2026-07-24T01:45:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4912 2024-03-06T10:35:32Z ddc:004 open_access

Solving Totally Unimodular LPs with the Shadow Vertex Algorithm Brunsch, Tobias Großwendt, Anna Röglin, Heiko linear optimization simplex algorithm shadow vertex method 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tobias Brunsch and Anna Großwendt and Heiko Röglin 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.171 urn:nbn:de:0030-drops-49125 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.171 eng https://creativecommons.org/licenses/by/3.0/legalcode