Pareto optimality and a class of set covering heuristics

DOI10.1007/BF02025298MaRDI QIDQ1309875zbMATH OpenOpenAlexFDO

Authors 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

dual saturation heuristicPareto optimal dual solutionset coveringworst-case performance

Mathematics Subject Classification ID

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

Recommendations

• RELAXATION HEURISTICS FOR THE SET COVERING PROBLEM(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)
• A theoretical justification of the set covering greedy heuristic of Caprara et al.
• An efficient heuristic for large set covering problems
• The set covering problem revisited: an empirical study of the value of dual information
• Conditional covering: greedy heuristics and computational results

Cites work

• A fast approximation algorithm for the multicovering problem
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A Sharp Bound on the Ratio Between Optimal Integer and Fractional Covers
• Approximation algorithms for combinatorial problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Economics for Mathematicians
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• Worst case analysis of a class of set covering heuristics

Cited in

(5)

• Pareto efficient solution and the class of \(\alpha\)-major efficient solutions
• A theoretical justification of the set covering greedy heuristic of Caprara et al.
• On interval and circular-arc covering problems
• The set covering problem revisited: an empirical study of the value of dual information
• Higher and lower-level knowledge discovery from Pareto-optimal sets

This page was built for publication: Pareto optimality and a class of set covering heuristics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1309875)