Accelerating the Multiplicative-Weights Framework for Graph Linear Programs скачать в хорошем качестве

Accelerating the Multiplicative-Weights Framework for Graph Linear Programs

Omri Weinstein (Hebrew U. & Columbia U.) https://simons.berkeley.edu/talks/omr... Dynamic Graphs and Algorithm Design 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.