Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search

DOI10.1137/060655225zbMath1185.68858OpenAlexW2019216770MaRDI QIDQ5189513

Asaf Levin

Publication date: 17 March 2010

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsset cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Related Items (12)

A-priori upper bounds for the set covering problem ⋮ Efficient Design of Compact Unstructured RNA Libraries Covering All k-mers ⋮ An Improved Approximation Bound for Spanning Star Forest and Color Saving ⋮ Unnamed Item ⋮ Tight approximation bounds for combinatorial frugal coverage algorithms ⋮ Overcoming controllability problems in distributed testing from an input output transition system ⋮ On the approximation ability of evolutionary optimization with application to minimum set cover ⋮ A local search algorithm for the \(k\)-path partition problem ⋮ Uniform unweighted set cover: the power of non-oblivious local search ⋮ A 6/5-approximation algorithm for the maximum 3-cover problem ⋮ Tight Approximation Bounds for Greedy Frugal Coverage Algorithms ⋮ Covering the edges of bipartite graphs using \(K_{2,2}\) graphs

This page was built for publication: Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search