<p>It is well known that simplex algorithm runs in exponential time in worst case.</p>

<ol>
<li><p>However are there situations (necessary and sufficient conditions) where simplex algorithm runs in polynomial time?</p></li>
<li><p>In particular does the simplex algorithm run in polynomial time on Bipartite Perfect matching polytopes and other non-trivial examples?</p></li>
</ol>

<p>Good references are welcome.</p>

CC BY-SA 4.0
2019-05-23T09:30:37.520Z
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).
Gamow
CC BY-SA 4.0
2019-05-23T09:31:49.770Z
@Gamow How is transportation polytope related to BPMP? Also how does diameter affect complexity of simplex algorithm?
Turbo
CC BY-SA 4.0
2019-05-23T11:17:44.677Z
Take $m=n$ and $c_j =1, r_i = 1$ for all $j,i$. The simplex visits vertices of the polytope.
PsySp
CC BY-SA 4.0
2019-05-23T19:03:34.663Z
See network simplex. https://en.wikipedia.org/wiki/Network_simplex_algorithm
Chandra Chekuri
CC BY-SA 4.0
2019-05-23T22:22:43.210Z
@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.
Turbo
CC BY-SA 4.0
2019-05-24T18:12:57.053Z
See Spielman and Teng, [Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time](https://arxiv.org/abs/cs/0111050).
Peter Shor 
CC BY-SA 4.0
2019-05-24T18:17:34.400Z
@PeterShor I thought in Bipartite Perfect Matching Polytopes (BPMP) it might be worst case polynomial time. What I mean is it will still be in polynomial time on convex hull of any subset of vertices of BPMPs (this is not guaranteed by network simplex algorithm).
Turbo
CC BY-SA 4.0
2019-05-24T20:42:31.523Z
@Brout: if you are trying to find a convex hull of a subset of vertices of a linear program, what guarantee do you have that it's still a linear program with a reasonable-size description?
Peter Shor 
CC BY-SA 4.0
2019-05-24T22:36:00.870Z
@PeterShor Assume simple description promise
Turbo
<linear-programming><matching><bipartite-graphs><simplex><extensionality>
Does simplex algorithm run in polynomial on Bipartite Perfect matching polytope?
Turbo
# Does simplex algorithm run in polynomial on Bipartite Perfect matching polytope?

(Asked by: username_0 on 2019-05-23)

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.

**Tags:** linear-programming, matching, bipartite-graphs, simplex, extensionality

> **Comments:**
> **username_1**: 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).  
> **username_0**: @username_1 How is transportation polytope related to BPMP? Also how does diameter affect complexity of simplex algorithm?  
> **username_2**: Take $m=n$ and $c_j =1, r_i = 1$ for all $j,i$. The simplex visits vertices of the polytope.  
> **username_3**: See network simplex. https://en.wikipedia.org/wiki/Network_simplex_algorithm  
> **username_0**: @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.  
> **username_4**: See Spielman and Teng, [Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time](https://arxiv.org/abs/cs/0111050).  
> **username_0**: @PeterShor I thought in Bipartite Perfect Matching Polytopes (BPMP) it might be worst case polynomial time. What I mean is it will still be in polynomial time on convex hull of any subset of vertices of BPMPs (this is not guaranteed by network simplex algorithm).  
> **username_4**: @Brout: if you are trying to find a convex hull of a subset of vertices of a linear program, what guarantee do you have that it's still a linear program with a reasonable-size description?  
> **username_0**: @PeterShor Assume simple description promise  

---

## 0 answers

