Randomized MWU for Positive LPs
Chandra Chekuri, Kent Quanrud · Society for Industrial and Applied Mathematics eBooks · 2018
We describe and analyze a simple randomized multiplicative weight update (MWU) based algorithm for approximately solving positive linear programming problems, in particular, mixed packing and covering LPs. Given m explicit linear packing and covering constraints over n variables specified by N nonzero entries, Young [36] gave a deterministic algorithm returning an (1 + ε)-approximate feasible solution (if a feasible solution exists) in Õ(N/ε2) time. We show that a simple randomized implementation matches this bound, and that randomization can be further exploited to improve the running time to Õ(N/ε + m/ε2 + n/ε3) (both with high probability). For instances that are not very sparse (with at least ῶ(1/ε) nonzeroes per column on average), this improves the running time of Õ(N/ε2). The randomized algorithm also gives improved running times for some implicitly defined problems that arise in combinatorial and geometric optimization.