Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
Open Access
- 14 June 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 229-236
Abstract
Positive linear programs (LP), also known as packing and covering linear programs, are an important class of problems that bridges computer science, operation research, and optimization. Efficient algorithms for solving such LPs have received significant attention in the past 20 years [2, 3, 4, 6, 7, 9, 11, 15, 16, 18, 19, 21, 24, 25, 26, 29, 30]. Unfortunately, all known nearly-linear time algorithms for producing (1+ε)-approximate solutions to positive LPs have a running time dependence that is at least proportional to ε-2. This is also known as an O(1/√T) convergence rate and is particularly poor in many applications. In this paper, we leverage insights from optimization theory to break this longstanding barrier. Our algorithms solve the packing LP in time ~O(N ε-1) and the covering LP in time ~O(N ε-1.5). At high level, they can be described as linear couplings of several first-order descent steps. This is the first application of our linear coupling technique (see [1]) to problems that are not amenable to blackbox applications known iterative algorithms in convex optimization. Our work also introduces a sequence of new techniques, including the stochastic and the non-symmetric execution of gradient truncation operations, which may be of independent interest.Keywords
Funding Information
- Simons Foundation (Graduate Student Award under grant no. 284059)
- National Science Foundation (CCF-1319460)
This publication has 23 references indexed in Scilit:
- A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear ProgramsAlgorithmica, 2013
- Distributed algorithms for multicommodity flow problems via approximate steepest descent frameworkACM Transactions on Algorithms, 2012
- Rounding of convex sets and efficient gradient methods for linear programming problemsOptimization Methods and Software, 2008
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing ProblemsSIAM Journal on Computing, 2007
- Smooth minimization of non-smooth functionsMathematical Programming, 2004
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point ProblemsSIAM Journal on Optimization, 2004
- Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow ControlSIAM Journal on Computing, 2004
- Approximating Fractional Multicommodity Flow Independent of the Number of CommoditiesSIAM Journal on Discrete Mathematics, 2000
- Parallel Approximation Algorithms by Positive Linear ProgrammingAlgorithmica, 1998
- A sublinear-time randomized approximation algorithm for matrix gamesOperations Research Letters, 1995