math.OC cs.CG
Short simplex paths in lattice polytopes. The goal of this paper is to design a simplex algorithm for linear programs on lattice polytopes that traces short' simplex paths from any given vertex to an optimal one. We consider a lattice polytope P contained in 0,k n and defined via m linear inequalities. Our first contribution is a simplex algorithm that reaches an optimal vertex by tracing a path along the edges of P of length in O(n 4 k log(nk) . The length of this path is independent from m and it is the best possible up to a polynomial function. In fact, it is only polynomially far from the worst case diameter, which roughly grows as a linear function in n and k . Motivated by the fact that most known lattice polytopes are defined via 0, pm 1 constraint matrices, our second contribution is an iterative algorithm which exploits the largest absolute value alpha of the entries in the constraint matrix. We show that the length of the simplex path generated by the iterative algorithm is in O(n 2k log(nk alpha)) . In particular, if alpha is bounded by a polynomial in n, k , then the length of the simplex path is in O(n 2k log(nk)) . For both algorithms, the number of arithmetic operations needed to compute the next vertex in the path is polynomial in n , m and log k . If k is polynomially bounded by n and m , the algorithm runs in strongly polynomial time.