A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem

DOI10.1137/S0097539704444750zbMath1086.68147OpenAlexW2083984856MaRDI QIDQ5700576

Refael Hassin, Asaf Levin

Publication date: 28 October 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539704444750

zbMATH Keywords

greedy algorithmapproximation algorithmsset cover problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (5)

On the approximation ability of evolutionary optimization with application to minimum set cover ⋮ Uniform unweighted set cover: the power of non-oblivious local search ⋮ Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP ⋮ Covering arrays via set covers ⋮ Problems and algorithms for covering arrays via set covers

This page was built for publication: A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem