Primal-Dual Schema for Capacitated Covering Problems

DOI10.1007/978-3-540-68891-4_20MaRDI QIDQ3503854zbMATH OpenOpenAlexFDO

Authors Tim Carnes, David B. Shmoys

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)

Recommendations

• Primal-dual schema for capacitated covering problems
• From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems
• scientific article; zbMATH DE number 2086430
• scientific article; zbMATH DE number 910865
• A water-filling primal-dual algorithm for approximating nonlinear covering problems

Cites work

• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
• An improved approximation algorithm for vertex cover with hard capacities
• Approximation Algorithms for the Multi-item Capacitated Lot-Sizing Problem Via Flow-Cover Inequalities
• Capacitated Facility Location: Valid Inequalities and Facets
• Covering Problems with Hard Capacities
• From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems
• Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems
• Primal-Dual Algorithms for Deterministic Inventory Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(24)

• Primal-dual algorithms for precedence constrained covering problems
• Improved algorithms for single machine scheduling with release dates and rejections
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• Bounding the price-of-fair-sharing using knapsack-cover constraints to guide near-optimal cost-recovery algorithms
• Primal-dual algorithms for precedence constrained covering problems
• A water-filling primal-dual algorithm for approximating nonlinear covering problems
• Resource allocation problem under single resource assignment
• LP-based approximation algorithms for capacitated facility location
• Tightening simple mixed-integer sets with guaranteed bounds
• Primal-dual schema for capacitated covering problems
• Integrality gaps for strengthened linear relaxations of capacitated facility location
• Minimum-cost mixed graph covers with targeted weight constraints
• Approximation algorithms for the partition vertex cover problem
• scientific article; zbMATH DE number 910865 (Why is no real title available?)
• Easy knapsacks and the complexity of energy allocation problems in the smart grid
• On generalizations of partial scenario set cover
• A primal-dual approximation algorithm for min-sum single-machine scheduling problems
• On set expansion problems and the small set expansion conjecture
• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems
• scientific article; zbMATH DE number 2086430 (Why is no real title available?)
• Supermodular covering knapsack polytope
• Maximizing coverage while ensuring fairness: a tale of conflicting objectives
• Precedence-constrained covering problems with multiplicity constraints
• Improved algorithm for resource allocation problems

This page was built for publication: Primal-Dual Schema for Capacitated Covering Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503854)