Solving Packing and Covering LPs in $\tilde{O}(\frac{1}{\epsilon^2})$ Distributed Iterations with a Single Algorithm and Simpler Analysis

Control of uncertain systems with a set-membership description of the uncertainty

D. P. Bertsekas · 1971

Earlier work this paper cites.

A parallel approximation algorithm for positive linear programming

M. Luby and N. Nisan · 1993

Earlier work this paper cites.

Linear programming without the matrix

C. Papadimitriou and M. Yannakakis · 1993

Earlier work this paper cites.

Fast approximation algorithms for fractional packing and covering problems

S. Plotkin, D. Shmoys, and É. Tardos · 1995

Earlier work this paper cites.

Global optimization using local information with applications to flow control

Y. Bartal, J. Byers, and D. Raz · 1997

Earlier work this paper cites.

Approximating fractional multicommodity flow independent of the number of commodities

L. Fleischer · 2000

Earlier work this paper cites.

Sequential and parallel algorithms for mixed packing and covering

Original

N. Young · 2001

Earlier work this paper cites.

Fast, distributed approximation algorithms for positive linear programming with applications to flow control

Y. Bartal, J. W. Byers, and D. Raz · 2004

Earlier work this paper cites.

Faster approximation algorithms for packing and covering problems

D. Bienstock and G. Iyengar · 2004

Cited alongside, same era.

Smooth minimization of non-smooth functions

Y. Nesterov · 2005

Cited alongside, same era.

The price of being near-sighted

F. Kuhn, T. Moscibroda, and R. Wattenhofer · 2006

Cited alongside, same era.

Faster and simpler algorithms for multicommodity flow and other fractional packing problems

N. Garg and J. Könemann · 2007

Cited alongside, same era.

Stateless distributed gradient descent for positive linear programs

B. Awerbuch and R. Khandekar · 2009

Cited alongside, same era.

The multiplicative weights update method: a meta-algorithm and applications

S. Arora, E. Hazan, and S. Kale · 2012

Cited alongside, same era.

A distributed algorithm for large-scale generalized matching

F. M. Manshadi, B. Awerbuch, R. Gemulla, R. Khandekar, J. Mestre, and M. Sozio · 2013

Later among the works it cites.

A nearly linear-time PTAS for explicit fractional packing and covering linear programs

C. Koufogiannakis and N. E. Young · 2014

Later among the works it cites.

Nearly-linear time positive LP solver with faster convergence rate

Z. Allen-Zhu and L. Orecchia · 2015

Later among the works it cites.

Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel

Z. Allen-Zhu and L. Orecchia · 2015

Later among the works it cites.

Efficient inverse maintenance and faster algorithms for linear programming

Y. T. Lee and A. Sidford · 2015

Later among the works it cites.

Unified acceleration method for packing and covering problems via diameter reduction