Absolute bounds on optimal cost for a class of set covering problems

DOI10.1007/BF01423649MaRDI QIDQ3818802zbMATH OpenOpenAlexFDO

Authors Nicholas G. Hall, Rakesh V. Vohra

Publication date 1989

Published in ZOR Zeitschrift f�r Operations Research Methods and Models of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

set coveringcirculantgreedy heuristicworst case

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27)

Recommendations

• A-priori upper bounds for the set covering problem
• A Sharp Bound on the Ratio Between Optimal Integer and Fractional Covers
• scientific article; zbMATH DE number 3863198
• A modified greedy heuristic for the set covering problem with improved worst case bound
• scientific article; zbMATH DE number 3869064

Cites work

• scientific article; zbMATH DE number 3512426 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A Guaranteed-Accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study

Cited in

(5)

• Minimax problems with bitonic matrices
• A-priori upper bounds for the set covering problem
• Bounds for optimal coverings
• A theoretical justification of the set covering greedy heuristic of Caprara et al.
• scientific article; zbMATH DE number 3869064 (Why is no real title available?)

This page was built for publication: Absolute bounds on optimal cost for a class of set covering problems

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