Primal-dual schema for capacitated covering problems

DOI10.1007/s10107-014-0803-zzbMath1327.90252OpenAlexW1964001041MaRDI QIDQ747765

David B. Shmoys, Tim Carnes

Publication date: 19 October 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-014-0803-z

zbMATH Keywords

approximation algorithmslot-sizingknapsack-cover inequalitiesprimal-dual schema

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27) Inventory, storage, reservoirs (90B05)

Related Items

A fast algorithm for the rectilinear distance location problem, A Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering Problems, Greedy algorithms for the single-demand facility location problem, Easy capacitated facility location problems, with connections to lot-sizing, Precedence-constrained covering problems with multiplicity constraints, A note on submodular function minimization with covering type linear constraints, An approximation algorithm for the partial covering 0-1 integer program, Unnamed Item

Cites Work

• Unnamed Item
• Single item lot-sizing with non-decreasing capacities
• 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
• Primal-Dual Schema for Capacitated Covering Problems
• Valid Linear Inequalities for Fixed Charge Problems
• 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
• A unified approach to approximating resource allocation and scheduling