Tight approximation bounds for combinatorial frugal coverage algorithms
From MaRDI portal
Publication:2392738
DOI10.1007/S10878-012-9464-0zbMATH Open1275.90077OpenAlexW2137185621MaRDI QIDQ2392738FDOQ2392738
Authors: I. Caragiannis, C. Kaklamanis, Maria Kyropoulou 
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
Recommendations
- Tight approximation bounds for greedy frugal coverage algorithms
- Tight approximation bounds for maximum multi-coverage
- Tight approximation bounds for maximum multi-coverage
- Tight bounds on subexponential time approximation of set cover and related problems
- Approximation algorithms for partial covering problems
- An approximation algorithm for the total covering problem
- scientific article; zbMATH DE number 1754596
- Partial sublinear time approximation and inapproximation for maximum coverage
- scientific article; zbMATH DE number 1163714
- On combinatorial approximation of covering 0-1 integer programs and partial set cover
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Cites Work
- A threshold of ln n for approximating set cover
- Approximation algorithms for combinatorial problems
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Title not available (Why is that?)
- Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
- 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
- Title not available (Why is that?)
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- Uniform unweighted set cover: the power of non-oblivious local search
- Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
- Oblivious algorithms for the maximum directed cut problem
- Wavelength management in WDM rings to maximize the number of connections
- Packing-based approximation algorithm for the \(k\)-set cover problem
- Donation center location problem
Cited In (10)
- Near-optimal asymmetric binary matrix partitions
- Tight bounds for double coverage against weak adversaries
- \(O(n \log n)\) procedures for tightening cover inequalities
- Tight approximation bounds for greedy frugal coverage algorithms
- Tight Bounds for Double Coverage Against Weak Adversaries
- Optimizing word set coverage for multi-event summarization
- Donation center location problem
- Tight bounds on subexponential time approximation of set cover and related problems
- Near-optimal asymmetric binary matrix partitions
- Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs.
This page was built for publication: Tight approximation bounds for combinatorial frugal coverage algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392738)
