3
$\begingroup$

The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.

After being open for decades, Francisco Santos has proved that this fails in general.

Assume we know the diameter of a polytope on which we do Simplex Programming.

  1. How does it affect the complexity of the algorithm?

  2. Can extended formulations reduce the complexity of Simplex algorithm?

In https://www.ems-ph.org/journals/newsletter/pdf/2012-12-86.pdf it is said

enter image description here

however connection is not clear.

Why is the Hirsch conjecture important to Simplex Complexity?

$\endgroup$
1
  • $\begingroup$ I do not understand the question: "Can extended formulations reduce the complexity of Simplex algorithm?" $\endgroup$
    – Gil Kalai
    Commented Jul 13, 2019 at 19:08

1 Answer 1

2
$\begingroup$

The diameter of the graph of the feasible polytope for a linear programming problem is indeed a lower bound for the number of pivot steps for the simplex algorithm when you start from a vertex and follow pivots steps all the way to the maximum. So if you find a version of the simplex algorithm for which the number of steps is provably polynomial (in $n$ the number of inequalities, and $d$ the number of variables) or even liner in $d$ and $n$ this will simultaneously give a polynomial [linear] version of the simplex algorithm and a polynomial [linear] upper bound on the diameter.

However in terms of what was proved so far the connections are not so clear.

1) The best upper bound on the diameter is of the type $n^{\log d}$. There is nothing as good (or even close) known for the algorithm (See 2)) .

2) The best version of the simplex algorithm requires (in expectation) $\exp (C \sqrt {d \log n})$ pivot steps.

3) For many pivot rules including the best known ones that are randomized, the (expected) number of steps in the worse case is $\exp d$ or $\exp (d^{c})$ where $c>0$.

4) The exponential lower bounds for 3) occur already for polytopes that are combinatorially equivalent to a $d$-cube, which have diameter $d$.

$\endgroup$
2
  • $\begingroup$ On extended formulation I thought there might be a way that simpler description could have a word in complexity of simplex algorithm. However from what you state with the standard interpretation of what a simplex algorithm is such a scenario is impossible. $\endgroup$
    – VS.
    Commented Jul 13, 2019 at 19:32
  • $\begingroup$ Are there any important open problems left in connection with Hirsch conjecture that possibly help understand complexity of simplex? $\endgroup$
    – VS.
    Commented Jul 13, 2019 at 19:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .