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 ∈ R~n : Ax ≤ b} along the edges of P, where A ∈ R~(m×n). Both, the length of the path and the running time of the algorithm, are polynomial in m, n, and a parameter 1/δ that is a measure for the flatness of the vertices of P. For integer matrices A ∈ Z~(m×n) we show a connection between δ and the largest absolute value Δ of any sub-determinant of A, yielding a bound of O(Δ~4mn~4) for the length of the computed path. This bound is expressed in the same parameter Δ as the recent non-constructive bound of O{Δ~2n~4 log(nΔ)) by Bonifas et al.. For the special case of totally unimodular matrices, the length of the computed path simplifies to O(mn~4), which significantly improves the previously best known constructive bound of O(m~(16)n~3 log~3 (mn)) by Dyer and Frieze.
展开▼
