Solving Covering / Packing LPs via Saddle-point Problems

Abstract

Packing linear programs $$max\{⟨c,x⟩:Ax\le b,x\ge 0\}$$ and their dual covering linear programs $$min\{⟨b,y⟩:A^{\mathrm{\top }}y\ge c,y\ge 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 of the 2-v-2 game to adopt other strategies. Based on joint work with Lorenzo Orecchia, and Erasmo Tani.