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

DOI10.1007/s10878-011-9417-zzbMath1269.90090OpenAlexW1965619131MaRDI 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 searchset packingapproximation algorithmsmaximum cover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (3)

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

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

This page was built for publication: A 6/5-approximation algorithm for the maximum 3-cover problem