Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence

DOI10.1007/S10107-018-1244-XzbMath1412.90081OpenAlexW2963555392MaRDI QIDQ2414908

Lorenzo Orecchia, Zeyuan Allen Zhu

Publication date: 17 May 2019

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-018-1244-x

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Linear programming (90C05) Numerical methods of relaxation type (49M20)

Related Items (2)

Multiplicative auction algorithm for approximate maximum weight bipartite matching ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• A nearly linear-time PTAS for explicit fractional packing and covering linear programs
• Parallel approximation algorithms by positive linear programming
• Approximating Fractional Multicommodity Flow Independent of the Number of Commodities
• Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
• Distributed algorithms for multicommodity flow problems via approximate steepest descent framework
• Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
• On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
• Linear-Time Approximation for Maximum Weight Matching
• Accelerated, Parallel, and Proximal Coordinate Descent
• Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems
• Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
• Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver
• Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
• Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• A parallel approximation algorithm for positive linear programming
• Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• QIP = PSPACE
• Rounding of convex sets and efficient gradient methods for linear programming problems

This page was built for publication: Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence