Approximating the Solution to Mixed Packing and Covering LPs in parallel time

TitleApproximating the Solution to Mixed Packing and Covering LPs in parallel time
Publication TypeConference Paper
Year of Publication2016
AuthorsMahoney, M. W., Rao S., Wang D., & Zhang P.

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


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.

ICSI Research Group

Big Data