A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem

DOI10.1007/978-3-540-85238-4_16MaRDI QIDQ3599128zbMATH OpenOpenAlexFDO

Authors I. Caragiannis, Gianpiero Monaco

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85238-4_16

Mathematics Subject Classification ID

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

Recommendations

• A 6/5-approximation algorithm for the maximum 3-cover problem
• An exact algorithm for the maximal covering problem
• An approximation algorithm for the total covering problem
• scientific article; zbMATH DE number 1947046
• On approximation of max-vertex-cover
• scientific article; zbMATH DE number 5371016
• An approximation algorithm for MAX 3-SAT
• Approximation algorithm for the multicovering problem
• Approximation algorithm for the partial set multi-cover problem
• A fast approximation algorithm for the multicovering 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 threshold of ln n for approximating set cover
• Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
• Approximating k-set cover and complementary graph coloring
• Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search
• Approximation algorithms for partial covering problems
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• 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
• Wavelength Management in WDM Rings to Maximize the Number of Connections

Cited in

(2)

• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• A 6/5-approximation algorithm for the maximum 3-cover problem

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 Q3599128)