[Theory] [Theory Lunch] Antares Chen (U. of Chicago), Wednesday 2/16, 12:30pm-1:30pm, JCL 390.

[Antares Chen]

************************************************************
**************************

*Date:* February 16, Wednesday
*Time: *12:30pm CT
*Location: *JCL 390

*Speaker:  Antares Chen (University of Chicago)*

*Title: **Solving Covering / Packing LPs via Saddle-point Problems*

*Zoom: *[link
<https://uchicago.zoom.us/j/95252312237?pwd=L3QxUjIvWXJlQWxjSzB6VVJqdFNhZz09>
]

*Abstract: *Packing linear programs $\max \{ \langle c, x \rangle : Ax \leq
b, x \geq 0 \}$ and their dual covering linear programs $\min \{ \langle b,
y \rangle : A^{\top}y \geq c, y \geq 0 \}$ are special cases of linear
programming where the variables, coefficients, and constraints are
non-negative. In this talk, we present some initial calculations that
derive an algorithm for approximately solving packing and covering LPs via
minimizing the duality gap -- the difference between the packing and
covering objectives. An interesting aspect of our calculations is that the
duality gap comes from reformulating the LP as a 2-v-2 game captured by a
saddle point problem. Our algorithm emerges by requiring players of the
game to adopt a specific strategy. However, other algorithms with
potentially faster convergence rates may emerge by requiring players to
adopt other strategies. Based on joint work with Lorenzo Orecchia, and
Erasmo Tani.

*Note*: We can now *serve lunch* on wednesdays.

[Theory Lunch Webpage <https://orecchia.net/event/theory-lunch/>]
[Theory Lunch Calendar
<https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago>
]

************************************************************
**************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220215/f03d221b/attachment.html>