Approximating the Solution to Mixed Packing and Covering LPs in parallel time
Title | Approximating the Solution to Mixed Packing and Covering LPs in parallel time |
Publication Type | Conference Paper |
Year of Publication | 2016 |
Authors | Mahoney, M. W., Rao S., Wang D., & Zhang P. |
Abstract | We study the problem of approximately solving positive linear programs (LPs). This class of LPs models a wide range of fundamental problems in combinatorial optimization and operations research, such as many resource allocation problems, solving non-negative linear systems, computing tomography, single/multi commodity flows on graphs, etc. For the special cases of pure packing or pure covering LPs, recent result by Allen-Zhu and Orecchia [2] gives O˜( 1 3 )-time parallel algorithm, which breaks the longstanding O˜( 1 4 ) running time bound by the seminal work of Luby and Nisan [10]. We present new parallel algorithm with running time O˜( 1 3 ) for the more general mixed packing and covering LPs, which improves upon the O˜( 1 4 )-time algorithm of Young [18,19]. Our work leverages the ideas from both the optimization oriented approach [2,17], as well as the more combinatorial approach with phases [18, 19]. In addition, our algorithm, when directly applied to pure packing or pure covering LPs, gives a improved running time of O˜( 1 2 ). |
Acknowledgment | We thank Richard Peng for helpful discussions on results and writing of the paper. DW was supported by ARO Grant W911NF-12-1-0541, SR was funded by NSF Grant CCF-1118083, and MM acknowledges the support of the NSF, AFOSR, and DARPA. |
URL | http://www.stat.berkeley.edu/~mmahoney/pubs/icalp16_mixedlps.pdf |
ICSI Research Group | Big Data |