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

DOI10.1007/BF01423649zbMath0666.90058OpenAlexW2093994969MaRDI QIDQ3818802

Nicholas G. Hall, Rakesh V. Vohra

Publication date: 1989

Published in: [https://portal.mardi4nfdi.de/entity/Q3031760 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)

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• A Greedy Heuristic for the Set-Covering Problem
• A Guaranteed-Accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering

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