Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs

DOI10.1007/s00224-008-9112-3zbMath1170.90461OpenAlexW1971391161MaRDI QIDQ839632

Stavros Athanassopoulos, Christos Kaklamanis, Ioannis Caragiannis

Publication date: 2 September 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-008-9112-3

zbMATH Keywords

combinatorial optimizationapproximation algorithmsset cover

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (15)

A new approximation algorithm for \(k\)-set cover problem ⋮ Tight approximation bounds for combinatorial frugal coverage algorithms ⋮ Approximating activation edge-cover and facility location problems ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Near-Optimal Asymmetric Binary Matrix Partitions ⋮ Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship ⋮ Uniform unweighted set cover: the power of non-oblivious local search ⋮ A 6/5-approximation algorithm for the maximum 3-cover problem ⋮ Near-optimal asymmetric binary matrix partitions ⋮ Boolean functions with long prime implicants ⋮ Tight Approximation Bounds for Greedy Frugal Coverage Algorithms ⋮ Unnamed Item ⋮ A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games ⋮ On the Complexity Landscape of the Domination Chain ⋮ Oblivious algorithms for the maximum directed cut problem

Cites Work

• Unnamed Item
• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• 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 the complexity of approximating \(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
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• A Greedy Heuristic for the Set-Covering Problem
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Non-approximability results for optimization problems on bounded degree instances
• Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search

This page was built for publication: Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs