2013/04/26 by Tobias Brunsch, Brunsch, Tobias, Heiko Röglin +1 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1304.7235
arxiv created 2013/04/26 · arxiv updated 2013/04/29
We show that the shadow vertex algorithm can be used to compute a short path between a given pair of vertices of a polytope P = x : Ax ≤ b along the edges of P, where A ∈ Rm × n is a real-valued matrix. Both, the length of the path and the running time of the algorithm, are polynomial in m, n, and a parameter 1/delta that is a measure for the flatness of the vertices of P. For integer matrices A ∈ Zm × n we show a connection between delta and the largest absolute value Delta of any sub-determinant of A, yielding a bound of O(Delta4 m n4) for the length of the computed path. This bound is expressed in the same parameter Delta as the recent non-constructive bound of O(Delta2 n4 log (n Delta)) by Bonifas et al. For the special case of totally unimodular matrices, the length of the computed path simplifies to O(m n4), which significantly improves the previously best known constructive bound of O(m16 n3 log3(mn)) by Dyer and Frieze.