# ARC Colloquium: Alberto Del Pia (WISC)

Event Details
• Date/Time:
• Monday October 19, 2020
11:00 am - 12:00 pm
• Location: Virtual via Bluejeans
• Phone:
• URL:
• Email:
• Fee(s):
N/A
• Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: Short simplex paths in lattice polytopes: Virtual via Bluejeans at 11:00am

Full Summary: No summary paragraph submitted.

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

In Campus Calendar
No
Groups

ARC

Invited Audience