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

DOI10.1007/11970125_23zbMath1129.68588OpenAlexW1594413663MaRDI QIDQ5443528

Asaf Levin

Publication date: 21 February 2008

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11970125_23

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items (9)

Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs ⋮ A new approximation algorithm for \(k\)-set cover problem ⋮ Approximating activation edge-cover and facility location problems ⋮ An improved approximation algorithm for the minimum 3-path partition problem ⋮ Boolean functions with long prime implicants ⋮ A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem ⋮ Unnamed Item ⋮ Approximation of the \(k\)-batch consolidation problem ⋮ A local search 4/3-approximation algorithm for the minimum 3-path partition problem

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