Primal-dual schema for capacitated covering problems

DOI10.1007/S10107-014-0803-ZMaRDI QIDQ747765zbMATH OpenOpenAlexFDO

Authors Tim Carnes, David B. Shmoys

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 algorithmsknapsack-cover inequalitieslot-sizingprimal-dual schema

Mathematics Subject Classification ID

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

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 910865
• scientific article; zbMATH DE number 2086430
• A water-filling primal-dual algorithm for approximating nonlinear covering problems

Cites work

• 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
• A unified approach to approximating resource allocation and scheduling
• 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
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• Primal-Dual Algorithms for Deterministic Inventory Problems
• Primal-Dual Schema for Capacitated Covering Problems
• Single item lot-sizing with non-decreasing capacities
• Valid Linear Inequalities for Fixed Charge Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(16)

• A fast algorithm for the rectilinear distance location problem
• Greedy algorithms for the single-demand facility location problem
• Easy capacitated facility location problems, with connections to lot-sizing
• An approximation algorithm for the partial covering 0-1 integer program
• Primal-Dual Schema for Capacitated Covering Problems
• Small extended formulation for knapsack cover inequalities from monotone circuits
• scientific article; zbMATH DE number 2086430 (Why is no real title available?)
• scientific article; zbMATH DE number 910865 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• A water-filling primal-dual algorithm for approximating nonlinear covering problems
• Precedence-constrained covering problems with multiplicity constraints
• A water-filling primal-dual algorithm for approximating nonlinear covering problems
• Approximation algorithms for solving the k-Chinese postman problem under interdiction budget constraints
• A note on submodular function minimization with covering type linear constraints
• Minimum-cost mixed graph covers with targeted weight constraints
• Online flexible busy time scheduling on heterogeneous machines

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 Q747765)