Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
A form of Klee-Minty formally proven?
5 views
Skip to first unread message
Axel Romihsita
Jun 4, 2015, 9:54:36 AM6/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.
One way would be to create a very explicit mapping from an index k to
the k-th tableau (k=1,...,2^n) in the execution of Dantzig's algorithm
on the above example.
Best,
Axel.
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.
One way would be to create a very explicit mapping from an index k to
the k-th tableau (k=1,...,2^n) in the execution of Dantzig's algorithm
on the above example.
Best,
Axel.
a_l_e_x_...@yahspamfuckoo.de
Jul 27, 2015, 1:56:14 AM7/27/15
to
This message was cancelled from within Mozilla Thunderbird.
--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---
--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---
0 new messages