Faster approximation algorithms for packing and covering problems

Keywords

Mathematics, Maximum flow problem, Separable space, Quadratic equation, Shortest path problem

References

• Approximate minimum-cost multicommodity flows in O (ɛ−2KNM) timetimeMichael D. Grigoriadis, Leonid G. Khachiyan — 1996
• Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and PracticeDaniel Bienstock — 2002
• Approximating fractional multicommodity flow independent of the number of commoditiesLisa Fleischer — 1999
• Fast algorithms for convex quadratic programming and multicommodity flowsSanjiv Kapoor, Pravin M. Vaidya — 1986
• Network Flows: Theory, Algorithms, and ApplicationsDavid K. Smith, Ravindra K. Ahuja, Thomas L. Magnanti — 1993
• A polynomial algorithm for minimum quadratic cost flow problemsMichel Minoux — 1984
• Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling ConstraintsMichael D. Grigoriadis, Leonid G. Khachiyan — 1994
• Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flowsDavid R. Karger, Serge Plotkin — 1995
• Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse CutsPhilip N. Klein, Serge Plotkin, Clifford Stein — 1994
• The flow deviation method: An approach to store-and-forward communication network designL. Fratta, Mário Gerla, Leonard Kleinrock — 1973
• Fast deterministic approximation for the multicommodity flow problemTomasz Radzik — 1995
• Asymptotic analysis of the flow deviation method for the maximum concurrent flow problemDaniel Bienstock, Olga Raskina — 2002
• Speeding-up linear programming using fast matrix multiplicationPravin M. Vaidya — 1989
• The maximum concurrent flow problemFarhad Shahrokhi, David W. Matula — 1990
• A new algorithm for minimizing convex functions over convex setsPravin M. Vaidya — 1989
• Geometric Algorithms and Combinatorial OptimizationMartin Grötschel, László Lovász, Alexander Schrijver — 1988
• Fast approximation algorithms for fractional packing and covering problemsSerge Plotkin, David B. Shmoys, Éva Tardos — 1991
• Fast approximation algorithms for multicommodity flow problemsTom Leighton, Clifford Stein, Fillia Makedon — 1991
• Faster and simpler algorithms for multicommodity flow and other fractional packing problemsNaveen Garg, Jochen Könemann — 1998
• A simple local-control approximation algorithm for multicommodity flowBaruch Awerbuch, T. Leighton — 1993

Cited by

• Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP SolverZeyuan Allen-Zhu, Yin Tat Lee, Lorenzo Orecchia — 2015
• Distributed storage allocations for neighborhood-based data accessDušan Jakovetić, Aleksandar Minja, Dragana Bajović — 2014
• Nearly-Linear Time Packing and Covering LP Solver with Faster Convergence Rate Than O(1/ε^2)Zeyuan Allen Zhu, Lorenzo Orecchia — 2014
• Nearly-Linear Time Positive LP Solver with Faster Convergence RateZeyuan Allen-Zhu, Lorenzo Orecchia — 2015
• Towards generic relation extractionBenjamin Clayton Hachey — 2009
• Multi-Document Summarisation Using Generic Relation ExtractionBen Hachey — 2009
• Using Optimization to Solve Positive LPs Faster in ParallelZeyuan Allen-Zhu, Lorenzo Orecchia — 2014
• Novel frameworks for auctions and optimizationZeyuan Allen-Zhu — 2015
• Nearly linear-time packing and covering LP solversZeyuan Allen-Zhu, Lorenzo Orecchia — 2014
• Solving Packing and Covering LPs in O(1ε^2) Distributed Iterations with a Single Algorithm and Simpler AnalysisJelena Diakonikolas, Lorenzo Orecchia — 2017
• Fast Approximation Algorithms for Positive Linear ProgramsDi Wang — 2017
• Nearly-Linear Time Packing and Covering LP Solver with Faster Convergence Rate Than O(1/" 2 )Zeyuan Allen-Zhu, L. Orecchia — 2014
• Dewey a Scaling Algorithm for Multicommodity Flow Problems a Scaling Algorithm for Multicommodity Flow ProblemsR. Schneur — 2008
• Approximation algorithms for linear programs and geometrically constrained packing roblemsPremiere DE Couverture, Florian Diedrich, Klaus Jansen — 2009
• Nearly-Linear Time Packing and Covering LP Solvers ( Achieving Width-Independence and O ( 1 / ε )-Convergence )L. Orecchia — 2016
• Multi-Document Summarisation Using Generic Relation Extraction Ben Hachey Centre for Languate Tecnology MacquarieBen Hachey — 2009

Related papers

• Sequential and parallel algorithms for mixed packing and coveringNeal E. Young — 2001
• A parallel approximation algorithm for positive linear programmingMichael Luby, Noam Nisan — 1993
• Smooth minimization of non-smooth functionsYu. Nesterov — 2005
• The Multiplicative Weights Update Method: a Meta-Algorithm and ApplicationsSanjeev Arora, Elad Hazan, Satyen Kale — 2012
• A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear ProgramsChristos Koufogiannakis, Neal E. Young — 2008
• Global optimization using local information with applications to flow controlY. Bartal, John W. Byers, D. Raz — 1997
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point ProblemsArkadi Nemirovski — 2004
• Utility-based decision-making in wireless sensor networksJohn W. Byers, Gabriel Nasser — 2000