Accelerating the Multiplicative-Weights Framework for Graph Linear Programs

Explore an advanced lecture on accelerating the multiplicative-weight updates (MWU) framework for solving packing and covering linear programs in graph optimization. Delve into the innovative approach of replacing the standard MWU iteration with a packing version of the Min-Inner-Product oracle. Discover how this modification significantly reduces the number of iterations required for an ε-approximate solution from Θ(m) to ~Θ(√m). Examine the potential for breaking the O(mn) runtime barrier in basic Network design LPs, such as Min Steiner Cut, by leveraging faster solutions to the Packing problem. Gain insights from the collaborative research of Omri Weinstein, Zhuan Khye Koh, and Sorrachai Yingchareonthawornchai, presented at the Simons Institute's Dynamic Graphs and Algorithm Design program.

Accelerating the Multiplicative-Weights Framework for Graph Linear Programs