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

DOI10.1007/BF01423649zbMATH Open0666.90058OpenAlexW2093994969MaRDI QIDQ3818802FDOQ3818802

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

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

zbMATH Keywords

set coveringcirculantgreedy heuristicworst case

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Approximation algorithms for combinatorial problems
• A Greedy Heuristic for the Set-Covering Problem
• On the ratio of optimal integral and fractional covers
• A Guaranteed-Accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• Title not available (Why is that?)

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.
• Title not available (Why is that?)

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)