Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
A form of Klee-Minty formally proven?
4 views
Skip to first unread message
Axel Romihsita
Jun 4, 2015, 12:35:08 PM6/4/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 mapping 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 mapping 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:49:56 AM7/27/15
to
This message was cancelled from within Mozilla Thunderbird.
0 new messages