A 6/5-approximation algorithm for the maximum 3-cover problem

DOI10.1007/s10878-011-9417-zzbMath1269.90090MaRDI QIDQ1945696

Gianpiero Monaco, Ioannis Caragiannis

Publication date: 8 April 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-011-9417-z

zbMATH Keywords

local search; set packing; approximation algorithms; maximum cover

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

Unnamed Item, Generalized budgeted submodular set function maximization, The multi-budget maximum weighted coverage problem

Cites Work

• Unnamed Item
• Unnamed Item
• Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Complexity of approximating bounded variants of optimization problems
• 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
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Approximation algorithms for partial covering problems
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• Wavelength Management in WDM Rings to Maximize the Number of Connections