Efficient parallel implementation of the multiplicative weight update method for graph-based linear programs

Caleb Ju, Serif Yesil, Mengyuan Sun +2

Positive linear programs (LPs) model many graph and operations research problems. One can solve for a $(1+\epsilon )$-approximation for positive LPs, for any selected $\epsilon$, in polylogarithm…