Worst case analysis of a class of set covering heuristics

DOI10.1007/BF01583786zbMath0489.90066MaRDI QIDQ3951908

Andrew C. Ho

Publication date: 1982

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

heuristic algorithmsset coveringgreedy heuristicworst case bounds

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Boolean programming (90C09)

Related Items (6)

Conditional covering: greedy heuristics and computational results ⋮ Two new heuristics for the location set covering problem ⋮ Dominant, an algorithm for the \(p\)-center problem. ⋮ Heuristic methods and applications: A categorized survey ⋮ Using a facility location algorithm to solve large set covering problems ⋮ Pareto optimality and a class of set covering heuristics

Cites Work

• 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

This page was built for publication: Worst case analysis of a class of set covering heuristics