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

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