Pareto optimality and a class of set covering heuristics

DOI10.1007/BF02025298zbMath0784.90060OpenAlexW1986373179MaRDI QIDQ1309875

Nicholas G. Hall, Rakesh V. Vohra

Publication date: 20 December 1993

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

Full work available at URL: https://doi.org/10.1007/bf02025298

zbMATH Keywords

worst-case performanceset coveringdual saturation heuristicPareto optimal dual solution

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

The set covering problem revisited: an empirical study of the value of dual information ⋮ On interval and circular-arc covering problems

Cites Work

• Unnamed Item
• A fast approximation algorithm for the multicovering problem
• Approximation algorithms for combinatorial problems
• A Sharp Bound on the Ratio Between Optimal Integer and Fractional Covers
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Economics for Mathematicians
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Worst case analysis of a class of set covering heuristics