<div dir="ltr"><div><div><div style=""><font size="4">******************************</font><span style="font-size:large">******************************</span><span style="font-size:large">**************************</span><br></div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b><br></b></font></div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b>Date:</b> February 16, Wednesday</font></div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b>Time: </b>12:30pm CT</font></div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b>Location: </b>JCL 390</font></div><div dir="auto" style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><b><font style="font-size:1.125rem"><br></font></b></div><div dir="auto" style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><b><font style="font-size:1.125rem">Speaker:  Antares Chen (University of Chicago)</font></b></div><div dir="auto" style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font size="4"><br></font></div><b style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem">Title: </font></b><font size="4"><b>Solving Covering / Packing LPs via Saddle-point Problems</b></font></div><div><b style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><br></font></b></div><div><span style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b>Zoom: </b>[<a href="https://uchicago.zoom.us/j/95252312237?pwd=L3QxUjIvWXJlQWxjSzB6VVJqdFNhZz09">link</a>]</font></span></div><div><br></div><div><div dir="auto"><font style="color:rgb(49,49,49);font-size:1.125rem;word-spacing:1px"><b style="font-size:1.125rem">Abstract: </b></font><font size="4">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.</font></div></div></div><div dir="auto"><font size="4"><br></font></div><div><font size="4"><b>Note</b>: </font><font size="4">We can now </font><font color="#313131"><span style="font-size:18px;word-spacing:1px"><b>serve lunch</b> on wednesdays.</span></font></div><div><span style="font-size:large"><br>[<a href="https://orecchia.net/event/theory-lunch/" target="_blank">Theory Lunch Webpage</a>]<br>[<a href="https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago" target="_blank">Theory Lunch Calendar</a>]</span></div><div dir="auto"><font size="4"><br></font></div><div dir="auto"><span style="font-size:large">******************************</span><span style="font-size:large">******************************</span><span style="font-size:large">**************************</span></div></div>