From Valid Inequalities to Heuristics: A Unified View of Primal-Dual Approximation Algorithms in Covering Problems

DOI10.1287/opre.46.4.503zbMath0979.90115OpenAlexW2008305525MaRDI QIDQ2770094

Chung-Piaw Teo, Dimitris J. Bertsimas

Publication date: 7 February 2002

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.46.4.503

zbMATH Keywords

coveringinteger programmingapproximation algorithmsprimal-dual methods

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

Using fractional primal-dual to schedule split intervals with demands ⋮ Primal-Dual Schema for Capacitated Covering Problems ⋮ Supermodular covering knapsack polytope ⋮ Local ratio with negative weights. ⋮ Primal-dual schema for capacitated covering problems