On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
From MaRDI portal
Publication:2944569
DOI10.1137/12087222XzbMATH Open1329.68126OpenAlexW2111940021MaRDI QIDQ2944569FDOQ2944569
Authors: 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
Recommendations
- scientific article; zbMATH DE number 1342139
- Approximation of optima of integer programs of the packing—covering type
- Approximation algorithms for covering/packing integer programs
- Primal-dual approximation algorithms for a packing-covering pair of problems
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- scientific article; zbMATH DE number 1263202
- Upper bounds on the average number of iterations for some algorithms of solving the set packing problem
- Parameterized approximation algorithms for packing problems
- Approximation Schemes for Covering and Packing
- scientific article; zbMATH DE number 1839427
Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) 2-person games (91A05)
Cites Work
- Smooth minimization of non-smooth functions
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Geometric algorithms and combinatorial optimization.
- Approximate max-min resource sharing for structured concave optimization
- A suggested computation for maximal multi-commodity network flows
- The Traveling-Salesman Problem and Minimum Spanning Trees
- A sublinear-time randomized approximation algorithm for matrix games
- The traveling-salesman problem and minimum spanning trees: Part II
- Adaptive game playing using multiplicative weights
- Simple strategies for large zero-sum games with applications to complexity theory
- The multiplicative weights update method: a meta-algorithm and applications
- Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
- Decomposition Principle for Linear Programs
- The maximum concurrent flow problem
- Title not available (Why is that?)
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
- The many facets of linear programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- How Hard Is It to Approximate the Best Nash Equilibrium?
- A Survey of Lagrangean Techniques for Discrete Optimization
- Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Potential function methods for approximately solving linear programming problems: theory and practice.
- Title not available (Why is that?)
- A nearly linear-time PTAS for explicit fractional packing and covering linear programs
- Nearly-linear time positive LP solver with faster convergence rate
- Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations
- Coordination Complexity of Parallel Price-Directive Decomposition
- Approximating semidefinite packing programs
- Fast approximation algorithms for multicommodity flow problems
- Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
Cited In (4)
- Extractor Lower Bounds, Revisited
- Bootstrap percolation with inhibition
- 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
This page was built for publication: On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944569)
