Difference between revisions of "Applied Algebra Seminar Spring 2020"
(→Spring 2020 Schedule)
|(One intermediate revision by the same user not shown)|
|Line 52:||Line 52:|
Revision as of 14:11, 10 February 2020
When: 11:00am, Thursdays
Where: 901 Van Vleck Hall
List: firstname.lastname@example.org, to join email email@example.com
Contact: Shamgar Gurevich, Jose Israel Rodriguez
Remark: We usually have a gap of around 2-3 weeks between seminars.
Spring 2020 Schedule
|February 20||Carla Michini (UW Madison)||Short simplex paths in lattice polytopes||Local|
|March 19||Spring Break|
|March 26||(Organizer traveling)|
|April 16||JM Landsberg (Texas A&M)||TBD||Jose|
Short simplex paths in lattice polytopes
We consider the problem of optimizing a linear function over a lattice polytope P contained in [0,k]^n and defined via m linear inequalities. We design a simplex algorithm that, given an initial vertex, reaches an optimal vertex by tracing a path along the edges of P of length at most O(n^6 k log k). The length of this path is independent on m and is the best possible up to a polynomial function, since it is only polynomially far from the worst case diameter. 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. This is a joint work with Alberto Del Pia.
Other events to note
|February 7||Talk: Inverse Problems, Imaging and Tensor Decomposition||Joe Kileel (Princeton)|
|February 10||Talk: Matroids, log-concavity, and expanders||Cynthia Vinzant (NCSU)|