DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2015.171

Solving Totally Unimodular LPs with the Shadow Vertex Algorithm

Authors: Tobias Brunsch, Anna Großwendt, and Heiko Röglin

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract

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/\delta, where \delta 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/delta) between two given vertices of a polyhedron [4]. Our result also complements a recent result due to Eisenbrand and Vempala [6] 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/\delta, 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/delta\le n and which have only O(n^2) constraints.

Cite as

Tobias Brunsch, Anna Großwendt, and Heiko Röglin. Solving Totally Unimodular LPs with the Shadow Vertex Algorithm. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 171-183, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{brunsch_et_al:LIPIcs.STACS.2015.171,
  author =	{Brunsch, Tobias and Gro{\ss}wendt, Anna and R\"{o}glin, Heiko},
  title =	{{Solving Totally Unimodular LPs with the Shadow Vertex Algorithm}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{171--183},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.171},
  URN =		{urn:nbn:de:0030-drops-49125},
  doi =		{10.4230/LIPIcs.STACS.2015.171},
  annote =	{Keywords: linear optimization, simplex algorithm, shadow vertex method}
}

Search Results

Documents authored by Brunsch, Tobias

Solving Totally Unimodular LPs with the Shadow Vertex Algorithm

Abstract

Cite as

Thanks for your feedback!

Could not send message