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

DOI10.1007/S00224-008-9112-3MaRDI QIDQ839632zbMATH OpenOpenAlexFDO

Authors Stavros Athanassopoulos, I. Caragiannis, C. Kaklamanis

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)

Recommendations

• Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
• Packing-based approximation algorithm for the \(k\)-set cover problem
• New and improved bounds for the minimum set cover problem
• A Tight Analysis of the Greedy Algorithm for Set Cover
• A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem

Cites work

• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A Tight Analysis of the Greedy Algorithm for Set Cover
• A modified greedy heuristic for the set covering problem with improved worst case bound
• A threshold of ln n for approximating set cover
• Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search
• Approximation algorithms for combinatorial problems
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Non-approximability results for optimization problems on bounded degree instances
• 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
• On the complexity of approximating \(k\)-set packing
• On the ratio of optimal integral and fractional covers

Cited in

(19)

• Approximation algorithms for the covering-type \(k\)-violation linear program
• Near-optimal asymmetric binary matrix partitions
• A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games
• A new approximation algorithm for k-set cover problem
• Packing-based approximation algorithm for the \(k\)-set cover problem
• On the complexity landscape of the domination chain
• Tight approximation bounds for greedy frugal coverage algorithms
• Boolean functions with long prime implicants
• Domination chain: characterisation, classical complexity, parameterised complexity and approximability
• Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
• Uniform unweighted set cover: the power of non-oblivious local search
• Approximating activation edge-cover and facility location problems
• Oblivious algorithms for the maximum directed cut problem
• A 6/5-approximation algorithm for the maximum 3-cover problem
• New and improved bounds for the minimum set cover problem
• scientific article; zbMATH DE number 7561664 (Why is no real title available?)
• Tight approximation bounds for combinatorial frugal coverage algorithms
• Near-optimal asymmetric binary matrix partitions
• Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q839632)