An Improved Approximation Bound for Spanning Star Forest and Color Saving
From MaRDI portal
Publication:3182915
DOI10.1007/978-3-642-03816-7_9zbMath1250.68285MaRDI QIDQ3182915
Ioannis Caragiannis, Christos Kaklamanis, Maria Kyropoulou, Stavros Athanassopoulos
Publication date: 16 October 2009
Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_9
Related Items
APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM, Improved approximation for spanning star forest in dense graphs, Tight approximation bounds for combinatorial frugal coverage algorithms, Improved approximation algorithms for the spanning star forest problem, On Variants of the Spanning Star Forest Problem, Tight Approximation Bounds for Greedy Frugal Coverage Algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Structure preserving reductions among convex optimization problems
- Toward a unified approach for the classification of NP-complete optimization problems
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Differential approximation algorithms for some combinatorial optimization problems
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- z-Approximations
- On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
- 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
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Improved Approximation Algorithms for the Spanning Star Forest Problem
- Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
- Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
- Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
- Computing and Combinatorics
- Wavelength Management in WDM Rings to Maximize the Number of Connections
