A modified greedy heuristic for the set covering problem with improved worst case bound
From MaRDI portal
Publication:1334632
DOI10.1016/0020-0190(93)90173-7zbMath0811.68099OpenAlexW2076146651MaRDI QIDQ1334632
Gang Yu, Dorit S. Hochbaum, Olivier Goldschmidt
Publication date: 25 September 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(93)90173-7
Related Items (13)
Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs ⋮ A new approximation algorithm for \(k\)-set cover problem ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ Improved approximation algorithms for minimum AND-circuits problem via \(k\)-set cover ⋮ Hybrid heuristic algorithms for set covering. ⋮ Uniform unweighted set cover: the power of non-oblivious local search ⋮ Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms ⋮ Constrained hitting set problem with intervals ⋮ Approximating k-set cover and complementary graph coloring ⋮ A modified greedy algorithm for dispersively weighted 3-set cover ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms ⋮ Covering the edges of bipartite graphs using \(K_{2,2}\) graphs ⋮ Stock selection heuristics for interdependent items
Cites Work
- Unnamed Item
- Unnamed Item
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- A Greedy Heuristic for the Set-Covering Problem
- The NP-Completeness of Some Edge-Partition Problems
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- On the Computational Complexity of Combinatorial Problems
This page was built for publication: A modified greedy heuristic for the set covering problem with improved worst case bound
