# Solving Totally Unimodular LPs with the Shadow Vertex Algorithm

arXiv: https://arxiv.org/abs/1412.5381 · HTML: https://mlsanity.com/paper/1412.5381/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2014.

## Built on by (most cited first, 1 of 1)

- [Fast Globally Optimal and Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2504.06385/) (2025)

## Abstract (arXiv)

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 constraints, and 1/δ, where δ is a parameter that measures the flatness of the vertices of the polyhedron. This extends our recent result that the shadow vertex algorithm finds paths of polynomial length (w.r.t. n, m, and 1/δ) between two given vertices of a polyhedron. Our result also complements a recent result due to Eisenbrand and Vempala who have shown that a certain version of the random edge pivot rule solves linear programs with a running time that is strongly polynomial in the number of variables n and 1/δ, but independent of the number m of constraints. Even though the running time of our algorithm depends on m, it is significantly faster for the important special case of totally unimodular linear programs, for which 1/δ≤ n and which have only O(n2) constraints.