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

Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu

Additional Information

In Campus Calendar
No
Groups

ARC

Invited Audience
Faculty/Staff, Postdoc, Graduate students, Undergraduate students
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: Francella Tonge
  • Workflow Status: Published
  • Created On: Aug 10, 2020 - 9:46am
  • Last Updated: Aug 26, 2020 - 9:52am