An Improved Approximation Bound for Spanning Star Forest and Color Saving
From MaRDI portal
Publication:3182915
DOI10.1007/978-3-642-03816-7_9zbMath1250.68285OpenAlexW1830560292MaRDI QIDQ3182915
Stavros Athanassopoulos, Maria Kyropoulou, Ioannis Caragiannis, Christos Kaklamanis
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 (16)
Tight approximation bounds for combinatorial frugal coverage algorithms ⋮ Improved approximation algorithms for the spanning star forest problem ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Near-Optimal Asymmetric Binary Matrix Partitions ⋮ Data reductions and combinatorial bounds for improved approximation algorithms ⋮ Improved approximation for spanning star forest in dense graphs ⋮ Near-optimal asymmetric binary matrix partitions ⋮ Local search algorithms for the maximum carpool matching problem ⋮ On the \(k\)-edge-incident subgraph problem and its variants ⋮ Combinatorics for smaller kernels: the differential of a graph ⋮ On Variants of the Spanning Star Forest Problem ⋮ Tight Approximation Bounds for Greedy Frugal Coverage Algorithms ⋮ APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM ⋮ Unnamed Item ⋮ On the star forest polytope for trees and cycles ⋮ Weighted Upper Edge Cover: Complexity and Approximability
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
This page was built for publication: An Improved Approximation Bound for Spanning Star Forest and Color Saving
