AMS Seminar w/ Carla Michini (University of Wisconsin-Madison) on Zoom

TITLE: Short simplex paths in lattice polytopes
ABSTRACT: We 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(n k)). The length of this path is independent of ‘m’ and is only polynomially far from the worst-case diameter, which roughly grows as nk.
Motivated by the fact that most known lattice polytopes are defined via 0,+1,-1 constraint matrices, our second contribution is a more sophisticated simplex algorithm which exploits the largest absolute value of the entries in the constraint matrix, denoted by ‘a’. We show that the length of the simplex path generated by this algorithm is in O(n^2 k log(n k a)). In particular, if the parameter ‘a’ is bounded by a polynomial in n, k, then the length of the simplex path is in O(n^2 k log(n k)). This is a joint work with Alberto Del Pia.

The cloud recording is now available.
Topic: AMS Department Seminar (Spring 2021)
Date: Feb 4, 2021 01:19 PM Eastern Time (US and Canada)
Recording for viewers:
https://wse.zoom.us/rec/share/mr4m196sKhWTcUV4TYKMWcT1MUxgUI7KdFoUhRxxrPBqew_OVKX0X7kG_Lee4jKN.kCmCor9FOsMzTuL5 Passcode: qB4+9D6q
Enjoy.