2026-07-26T00:22:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6333 2024-03-06T10:37:44Z ddc:004 open_access

Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time Mahoney, Michael W. Rao, Satish Wang, Di Zhang, Peng Mixed packing and covering Linear program Approximation algorithm Parallel algorithm 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 [Allen/Zhu/Orecchia, SODA'15] gives O˜(1/(epsilon^3))-time parallel algorithm, which breaks the longstanding O˜(1/(epsilon^4)) running time bound by the seminal work of Luby and Nisan [Luby/Nisan, STOC'93]. We present new parallel algorithm with running time O˜(1/(epsilon^3)) for the more general mixed packing and covering LPs, which improves upon the O˜(1/(epsilon^4))-time algorithm of Young [Young, FOCS'01; Young, arXiv 2014]. Our work leverages the ideas from both the optimization oriented approach [Allen/Zhu/Orecchia, SODA'15; Wang/Mahoney/Mohan/Rao, arXiv 2015], as well as the more combinatorial approach with phases [Young, FOCS'01; Young, arXiv 2014]. In addition, our algorithm, when directly applied to pure packing or pure covering LPs, gives a improved running time of O˜(1/(epsilon^2)). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael W. Mahoney and Satish Rao and Di Wang and Peng Zhang 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.52 urn:nbn:de:0030-drops-63335 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.52 eng https://creativecommons.org/licenses/by/3.0/legalcode