文章基本信息

标题：Solving Totally Unimodular LPs with the Shadow Vertex Algorithm
本地全文：下载
作者：Tobias Brunsch ; Anna Gro{\ss}wendt ; Heiko R{\"o}glin 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：30
页码：171-183
DOI：10.4230/LIPIcs.STACS.2015.171
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：linear optimization; simplex algorithm; shadow vertex method