Primal-Dual Schema for Capacitated Covering Problems

DOI10.1007/978-3-540-68891-4_20zbMath1143.90375OpenAlexW1531390321MaRDI QIDQ3503854

David B. Shmoys, Tim Carnes

Publication date: 10 June 2008

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-68891-4_20

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Integrality gaps for strengthened linear relaxations of capacitated facility location, Primal-Dual Algorithms for Precedence Constrained Covering Problems, Resource allocation problem under single resource assignment, Primal-dual algorithms for precedence constrained covering problems, Sum-of-squares hierarchy lower bounds for symmetric formulations, Tightening simple mixed-integer sets with guaranteed bounds, Improved Algorithm for Resource Allocation Problems, Maximizing coverage while ensuring fairness: a tale of conflicting objectives, LP-based approximation algorithms for capacitated facility location, On set expansion problems and the small set expansion conjecture, Supermodular covering knapsack polytope, Easy knapsacks and the complexity of energy allocation problems in the smart grid, Approximation algorithms for the partition vertex cover problem, Primal-dual schema for capacitated covering problems, A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems, Precedence-constrained covering problems with multiplicity constraints, A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems, Improved algorithms for single machine scheduling with release dates and rejections

Cites Work

• Unnamed Item
• An improved approximation algorithm for vertex cover with hard capacities
• From Valid Inequalities to Heuristics: A Unified View of Primal-Dual Approximation Algorithms in Covering Problems
• Covering Problems with Hard Capacities
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Capacitated Facility Location: Valid Inequalities and Facets
• Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
• Primal-Dual Algorithms for Deterministic Inventory Problems
• Approximation Algorithms for the Multi-item Capacitated Lot-Sizing Problem Via Flow-Cover Inequalities
• Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems