Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
A form of Klee-Minty formally proven?
2 views
Skip to first unread message
Axel Romihsita
Jun 9, 2015, 8:56:54 AM6/9/15
to
Dear all:
Is there a source (book/script/...) which gives a complete and fully
formal proof that the simplex algorithm (in its max-form) with Dantzig's
rule requires 2^n different tableaux on the following Klee-Minty-kind
example:
maximize $\sum_{i=1}^n 2^{n-i}x_i$
subject to for all $i\in\{1,...,n\}$:
$\sum_{j=1}^{i-1} 2^{i-j+1}x_j + x_i \le 5^i$
?
All sources I found just treat other examples and/or leave the key proof
details to the reader.
Essentially, we need an explicit map from an index k to the k-th tableau
(k=0,...,2^n-1) in the execution of Dantzig's algorithm on the above
example.
Best,
Axel.
--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---
Is there a source (book/script/...) which gives a complete and fully
formal proof that the simplex algorithm (in its max-form) with Dantzig's
rule requires 2^n different tableaux on the following Klee-Minty-kind
example:
maximize $\sum_{i=1}^n 2^{n-i}x_i$
subject to for all $i\in\{1,...,n\}$:
$\sum_{j=1}^{i-1} 2^{i-j+1}x_j + x_i \le 5^i$
?
All sources I found just treat other examples and/or leave the key proof
details to the reader.
Essentially, we need an explicit map from an index k to the k-th tableau
(k=0,...,2^n-1) in the execution of Dantzig's algorithm on the above
example.
Best,
Axel.
--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---
a_x_e_l_...@yahfuckspamoo.de
Jul 27, 2015, 1:52:36 AM7/27/15
to
This message was cancelled from within Mozilla Thunderbird.
0 new messages