It is well known that simplex algorithm runs in exponential time in worst case.

  1. However are there situations (necessary and sufficient conditions) where simplex algorithm runs in polynomial time?

  2. In particular does the simplex algorithm run in polynomial time on Bipartite Perfect matching polytopes and other non-trivial examples?

Good references are welcome.

  • $\begingroup$ You may start with reading the paper by Brightwell, Van den Heuvel, Stougie: "A linear bound on the diameter of the transportation polytope." Combinatorica 26:133-139 (2006). $\endgroup$
    – Gamow
    May 23 '19 at 9:30
  • $\begingroup$ @Gamow How is transportation polytope related to BPMP? Also how does diameter affect complexity of simplex algorithm? $\endgroup$
    – Mr.
    May 23 '19 at 9:31
  • $\begingroup$ Take $m=n$ and $c_j =1, r_i = 1$ for all $j,i$. The simplex visits vertices of the polytope. $\endgroup$
    – PsySp
    May 23 '19 at 11:17
  • $\begingroup$ See network simplex. en.wikipedia.org/wiki/Network_simplex_algorithm $\endgroup$ May 23 '19 at 19:03
  • $\begingroup$ @ChandraChekuri Not sure if network simplex is a linear programming technique. Or an algorithm through graph theory which is inspired from simplex. With simplex we know for sure it is lp algorithm. Given linear conditions and objective we optimize. The essential problem here is then if the polytope is from bipartite graph then do we run in polynomial time. $\endgroup$
    – Mr.
    May 23 '19 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.