Tight approximation bounds for combinatorial frugal coverage algorithms
From MaRDI portal
Publication:2392738
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
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