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

DOI10.1007/978-3-540-85238-4_16zbMath1173.90507OpenAlexW1606598340MaRDI QIDQ3599128

Gianpiero Monaco, Ioannis Caragiannis

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• 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
• Approximating k-set cover and complementary graph coloring
• Approximation algorithms for partial covering problems
• Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search
• Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
• 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