Tight approximation bounds for combinatorial frugal coverage algorithms

DOI10.1007/s10878-012-9464-0zbMath1275.90077OpenAlexW2137185621MaRDI QIDQ2392738

Christos Kaklamanis, Maria Kyropoulou, Ioannis Caragiannis

Publication date: 2 August 2013

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

Full work available at URL: https://ora.ox.ac.uk/objects/uuid:b9267fda-ca9d-4408-bae0-927e6e89677d

zbMATH Keywords

set packingapproximation algorithmsset coverfrugal coverage

Mathematics Subject Classification ID

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

Related Items

Near-Optimal Asymmetric Binary Matrix Partitions ⋮ Optimizing word set coverage for multi-event summarization ⋮ Near-optimal asymmetric binary matrix partitions

Cites Work

• Unnamed Item
• Unnamed Item
• Uniform unweighted set cover: the power of non-oblivious local search
• Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
• Approximation algorithms for combinatorial problems
• Oblivious algorithms for the maximum directed cut problem
• Donation Center Location Problem
• Packing-Based Approximation Algorithm for the k-Set Cover Problem
• A threshold of ln n for approximating set cover
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• 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
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• 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: Tight approximation bounds for combinatorial frugal coverage algorithms