Randomized MWU for positive LPs

Chandra Chekuri, Kent Quanrud

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Pages358-377
Number of pages20
ISBN (Electronic)9781611975031
DOIs
StatePublished - 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Country/TerritoryUnited States
CityNew Orleans
Period1/7/181/10/18

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Randomized MWU for positive LPs'. Together they form a unique fingerprint.

Cite this