ARC Colloquium: Alberto Del Pia (WISC)

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.

----------------------------------

Speaker's Webpage

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

Event Details

Date/Time:

  • Monday, October 19, 2020
    12:00 pm - 1:00 pm