Uniform unweighted set cover: the power of non-oblivious local search

DOI10.1016/j.tcs.2010.12.004zbMath1211.68513OpenAlexW1991242013MaRDI QIDQ631761

Asaf Levin, Uri Yovel

Publication date: 14 March 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.12.004

zbMATH Keywords

local searchapproximation algorithmsset coverunweighted \(k\)-set cover problemunweighted set cover problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items (2)

Tight approximation bounds for combinatorial frugal coverage algorithms ⋮ Tight Approximation Bounds for Greedy Frugal Coverage Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• A modified greedy heuristic for the set covering problem with improved worst case bound
• On Local Search for Weighted k-Set Packing
• A threshold of ln n for approximating set cover
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• A Greedy Heuristic for the Set-Covering Problem
• On Syntactic versus Computational Views of Approximability
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• Covering the Edges of Bipartite Graphs Using K 2,2 Graphs
• A Survey of Approximation Results for Local Search Algorithms
• A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem

This page was built for publication: Uniform unweighted set cover: the power of non-oblivious local search