Algorithms & Randomness Center (ARC)
Alberto Del Pia (WISC)
Monday, October 19, 2020
Virtual via Bluejeans - 11:00 am
Title: Short simplex paths in lattice polytopes
Abstract: In this talk we discuss the problem of designing 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 on 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,±1 constraint matrices, our second contribution is an iterative algorithm which exploits the largest absolute value α 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^2 k log(nkα)). In particular, if α is bounded by a polynomial in n, k, then the length of the simplex path is in O(n^2 k 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.
----------------------------------
Videos of recent talks are available at: http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
