Tight approximation bounds for greedy frugal coverage algorithms

DOI10.1007/978-3-642-21204-8_22MaRDI QIDQ3004668zbMATH OpenOpenAlexFDO

Authors I. Caragiannis, C. Kaklamanis, Maria Kyropoulou

Publication date 3 June 2011

Published in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-21204-8_22

Mathematics Subject Classification ID

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

Recommendations

• Tight approximation bounds for combinatorial frugal coverage algorithms
• A Tight Analysis of the Greedy Algorithm for Set Cover
• scientific article; zbMATH DE number 1323125
• Improved greedy algorithm for maximum coverage problem with group budget constraints
• Covering analysis of the greedy algorithm for partial cover

Cites work

• A threshold of ln n for approximating set cover
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• Analysis of approximation algorithms for k-set cover using factor-revealing linear programs
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• Approximation algorithms for combinatorial problems
• Donation center location problem
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Oblivious algorithms for the maximum directed cut problem
• Uniform unweighted set cover: the power of non-oblivious local search
• Wavelength management in WDM rings to maximize the number of connections

Cited in

(5)

• \(O(n \log n)\) procedures for tightening cover inequalities
• Tight bounds for double coverage against weak adversaries
• Tight approximation bounds for combinatorial frugal coverage algorithms
• Tight Bounds for Double Coverage Against Weak Adversaries
• Donation center location problem

This page was built for publication: Tight approximation bounds for greedy frugal coverage algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3004668)