Is the Simplex Method still polynomial when all inequalities are through the origin? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T21:34:56Z http://mathoverflow.net/feeds/question/95068 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/95068/is-the-simplex-method-still-polynomial-when-all-inequalities-are-through-the-orig Is the Simplex Method still polynomial when all inequalities are through the origin? GB 2012-04-24T20:47:16Z 2012-04-24T21:29:51Z <p>Hello,</p> <p>I want to solve a linear program using the simplex method, and I know that all my inequalities will pass through the origin (therefore, either my initial solution of (0, ... , 0) is optimal, or the program is unbounded; I'm only really interested in distinguishing between these two cases).</p> <p>So here's how I think the algorithm would work: Step one is to pick a pivot variable. Step two - and here's where I think things break down - is to find the equation with the smallest value of the constant to the coefficient of the pivot variable. But since my inequalities all pass through the origin, the constant is 0 every time, so all equations are an equally valid choice for the pivot. This reduces the Simplex Method to a brute-force search of the set of basic variables, which would make it run in above-polynomial time.</p> <p>Is this correct? Or am I missing some feature of the Simplex Method that handles this case?</p> <p>Thanks in advance!</p> http://mathoverflow.net/questions/95068/is-the-simplex-method-still-polynomial-when-all-inequalities-are-through-the-orig/95076#95076 Answer by Pascal Maillard for Is the Simplex Method still polynomial when all inequalities are through the origin? Pascal Maillard 2012-04-24T21:29:51Z 2012-04-24T21:29:51Z <p>As far as I can recall, the Simplex Algorithm is <em>not</em> running in polynomial time, although when randomly perturbing the input, it runs on average in polynomial time (this is also studied under the name "Smoothed Analysis of Algorithms", see for example the article by Spielman and Teng, Journal of the ACM, Vol. 51, No. 3, May 2004, pp. 385–463 <a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;ved=0CC0QFjAA&amp;url=http%3A%2F%2Fwww.cs.duke.edu%2Fcourses%2Fspring07%2Fcps296.2%2Fpapers%2Fp385-a_spielman.pdf&amp;ei=6BmXT7GONuas0QXig_2yDg&amp;usg=AFQjCNE5PFNqSIUgHjNdVys2dX_drjkUAg&amp;sig2=ItkEJelYbgxu-yO6NOuidA" rel="nofollow">http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;ved=0CC0QFjAA&amp;url=http%3A%2F%2Fwww.cs.duke.edu%2Fcourses%2Fspring07%2Fcps296.2%2Fpapers%2Fp385-a_spielman.pdf&amp;ei=6BmXT7GONuas0QXig_2yDg&amp;usg=AFQjCNE5PFNqSIUgHjNdVys2dX_drjkUAg&amp;sig2=ItkEJelYbgxu-yO6NOuidA</a></p> <p>There are however algorithms for linear programming which run in polynomial time, known as "inner-point" algorithms, because they traverse the interior of the simplex.</p>