Nearly linear-time packing and covering LP solvers: Achieving width-independence and -convergence

摘要

Packing and covering linear programs (PC-LP s) form an important class of linear programs (LPs) across computer science, operations research, and optimization. Luby and Nisan(in: STOC, ACM Press, New York, 1993) constructed an iterative algorithm for approximately solving PC-LP s in nearly linear time, where the time complexity scales nearly linearly in N, the number of nonzero entries of the matrix, and polynomially in epsilon, the (multiplicative) approximation error. Unfortunately, existing nearly linear-time algorithms(Plotkin et al. in Math Oper Res 20(2):257-301, 1995; Bartal et al., in: Proceedings 38th annual symposium on foundations of computer science, IEEE Computer Society, 1997; Young, in: 42nd annual IEEE symposium on foundations of computer science (FOCS'01), IEEE Computer Society, 2001; Koufogiannakis and Young in Algorithmica 70:494-506, 2013; Young in Nearly linear-time approximation schemes for mixed packing/covering and facility-location linear programs, 2014. arXiv:1407.3015; Allen-Zhu and Orecchia, in: SODA, 2015) for solving PC-LP s require time at least proportional to epsilon-2. In this paper, we break this longstanding barrier by designing a packing solver that runs in time O(N epsilon-1) and covering LP solver that runs in time O(N epsilon-1.5). Our packing solver can be extended to run in time O-1) for a class of well-behaved covering programs. In a follow-up work, Wang et al. (in: ICALP, 2016) showed that all covering LPs can be converted into well-behaved ones by a reduction that blows up the problem size only logarithmically.