文章基本信息

标题：Approximating the Solution to Mixed Packing and Covering LPs in Parallel O~(epsilon^{-3}) Time
本地全文：下载
作者：Michael W. Mahoney ; Satish Rao ; Di Wang 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：52:1-52:14
DOI：10.4230/LIPIcs.ICALP.2016.52
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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)).
关键词：Mixed packing and covering; Linear program; Approximation algorithm; Parallel algorithm