Solving Totally Unimodular LPs with the Shadow Vertex Algorithm

Tobias Brunsch, Anna Großwendt, Heiko Röglin

We show that the shadow vertex simplex algorithm can be used to solve linear programs in strongly polynomial time with respect to the number $n$ of variables, the number $m$ of con…