TY - GEN

T1 - Randomized MWU for positive LPs

AU - Chekuri, Chandra

AU - Quanrud, Kent

N1 - Publisher Copyright:
© Copyright 2018 by SIAM.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85045582613&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045582613&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.25

DO - 10.1137/1.9781611975031.25

M3 - Conference contribution

AN - SCOPUS:85045582613

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 358

EP - 377

BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

A2 - Czumaj, Artur

PB - Association for Computing Machinery

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Y2 - 7 January 2018 through 10 January 2018

ER -