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

DOI10.1007/S00224-008-9112-3zbMATH Open1170.90461OpenAlexW1971391161MaRDI QIDQ839632FDOQ839632

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

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmsset cover

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (18)

• Approximation algorithms for the covering-type \(k\)-violation linear program
• 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
• Near-Optimal Asymmetric Binary Matrix Partitions
• 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
• Approximating activation edge-cover and facility location problems
• Uniform unweighted set cover: the power of non-oblivious local search
• On the Complexity Landscape of the Domination Chain
• Oblivious algorithms for the maximum directed cut problem
• A 6/5-approximation algorithm for the maximum 3-cover problem
• Title not available (Why is that?)
• 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)