Brunsch, Tobias ;
Großwendt, Anna ;
Röglin, Heiko
Solving Totally Unimodular LPs with the Shadow Vertex Algorithm
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.
BibTeX  Entry
@InProceedings{brunsch_et_al:LIPIcs:2015:4912,
author = {Tobias Brunsch and Anna Gro{\ss}wendt and Heiko R{\"o}glin},
title = {{Solving Totally Unimodular LPs with the Shadow Vertex Algorithm}},
booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages = {171183},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897781},
ISSN = {18688969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4912},
URN = {urn:nbn:de:0030drops49125},
doi = {10.4230/LIPIcs.STACS.2015.171},
annote = {Keywords: linear optimization, simplex algorithm, shadow vertex method}
}
2015
Keywords: 

linear optimization, simplex algorithm, shadow vertex method 
Seminar: 

32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Issue date: 

2015 
Date of publication: 

2015 