# Tag Info

8

This answer is for your "somewhat related question": In the following recent paper, Klee-Minty cubes were used explicitly to show that there exists a pivoting rule for the simplex method (not one of the standard ones, like Dantzig's pivoting rule analysed by Disser and Skutella) for which it is PSPACE-complete to decide whether a variable enters the basis ...

2

The first thing that comes to mind is "Smoothed Analysis" of Spielman and Teng: arxiv.org/pdf/cs/0111050.pdf. Their main result is Theorem 5.0.1, which bounds the expected (over "typical instances") runtime of a version of the Simplex algorithm by a polynomial, though the degree of the polynomial is not stated there.

1

I'd suggest using a recursive search. Suppose you have a subset of $k$ of the points and a proposed allocation for those $k$ points into X/Y/Z. Then you can test whether there exists $w_x,w_y,w_z$ that would lead to that allocation, by testing feasibility of a linear program. (For the allocation to be feasible, there are a bunch of linear inequalities ...

1

In 2019, the opensource LP solver GLPK does the Klee-Minty cube problem with $D=200$ in under 100 milliseconds, on a 2.7 GHz iMac: GLPK Simplex Optimizer, v4.65 200 rows, 200 columns, 20100 non-zeros Preprocessing... 199 rows, 200 columns, 20099 non-zeros Scaling... A: min|aij| = 1.000e+00 max|aij| = 1.607e+60 ratio = 1.607e+60 ... Constructing ...

Only top voted, non community-wiki answers of a minimum length are eligible