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

DOI10.1007/S10878-011-9417-ZMaRDI QIDQ1945696zbMATH OpenOpenAlexFDO

Authors I. Caragiannis, Gianpiero Monaco

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

approximation algorithmslocal searchmaximum coverset packing

Mathematics Subject Classification ID

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

Recommendations

• A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
• A new approximation algorithm for k-set cover problem
• Packing-based approximation algorithm for the k-set cover problem
• The budgeted maximum coverage problem
• A modified greedy algorithm for dispersively weighted 3-set cover

Cites work

• A threshold of ln n for approximating set cover
• Analysis of approximation algorithms for k-set cover using factor-revealing linear programs
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• Approximation algorithms for partial covering problems
• Complexity of approximating bounded variants of optimization problems
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• 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
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Wavelength management in WDM rings to maximize the number of connections

Cited in

(5)

• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• Generalized budgeted submodular set function maximization
• The multi-budget maximum weighted coverage problem
• A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
• Generalized budgeted submodular set function maximization

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

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