Primal-dual schema for capacitated covering problems
From MaRDI portal
Publication:747765
DOI10.1007/s10107-014-0803-zzbMath1327.90252OpenAlexW1964001041MaRDI QIDQ747765
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
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