Abstract
We present an accelerated version of the multiplicative-weight updates (MwU) framework for solving packing/covering LPs (Garg-Konemann'98, Madry'10). Such LPs capture many important graph optimization problems including multicommodity flows, Steiner cuts and other Network Design problems. Our key idea is replacing the vanilla MwU iteration (decremental
Min-Inner-Product of a vector with the path-matrix) with a *packing* version of the Min-IP oracle (which needs to return a maximally-disjoint set of paths with small inner-products, reminiscent of blocking-flows).
We show that with this oracle, the number of MwU iterations required to achieve ε-approximate solution for the LP, is decreased from Θ(m) to ~Θ(√m), which is optimal. We then outline a direction for breaking the well-known O(mn)
runtime barrier for basic Network design LPs (e.g., Min Steiner Cut), by showing that the Packing problem can be solved *faster* than the Decremental Min-IP problem.
Joint work with Zhuan Khye Koh and Sorrachai Yingchareonthawornchai.