On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
From MaRDI portal
Publication:2944569
DOI10.1137/12087222XzbMath1329.68126OpenAlexW2111940021MaRDI QIDQ2944569
Neal E. Young, Philip N. Klein
Publication date: 2 September 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/12087222x
Linear programming (90C05) 2-person games (91A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence ⋮ Approximate Degree, Secret Sharing, and Concentration Phenomena ⋮ Extractor Lower Bounds, Revisited ⋮ Bootstrap percolation with inhibition
Cites Work
- Unnamed Item
- 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
- Geometric algorithms and combinatorial optimization.
- Potential function methods for approximately solving linear programming problems: theory and practice.
- Adaptive game playing using multiplicative weights
- The many facets of linear programming
- Fast approximation algorithms for multicommodity flow problems
- A sublinear-time randomized approximation algorithm for matrix games
- Approximate Max-Min Resource Sharing for Structured Concave Optimization
- A Suggested Computation for Maximal Multi-Commodity Network Flows
- Simple strategies for large zero-sum games with applications to complexity theory
- Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
- How Hard Is It to Approximate the Best Nash Equilibrium?
- Approximating Semidefinite Packing Programs
- Decomposition Principle for Linear Programs
- The maximum concurrent flow problem
- Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems
- A Survey of Lagrangean Techniques for Discrete Optimization
- Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
- 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
- Coordination Complexity of Parallel Price-Directive Decomposition
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
- Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations
- The Traveling-Salesman Problem and Minimum Spanning Trees
- The traveling-salesman problem and minimum spanning trees: Part II
