Approximating k-set cover and complementary graph coloring
From MaRDI portal
Publication:4645918
DOI10.1007/3-540-61310-2_10zbMath1415.90103OpenAlexW1536142435MaRDI QIDQ4645918
Publication date: 11 January 2019
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-61310-2_10
Related Items (12)
Exact algorithms and applications for tree-like Weighted Set Cover ⋮ Probabilistic distributed algorithms for energy efficient routing and tracking in wireless sensor networks ⋮ Bridging gap between standard and differential polynomial approximation: The case of bin-packing ⋮ On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion ⋮ Dual parameterization of Weighted Coloring ⋮ Partition into cliques for cubic graphs: Planar case, complexity and approximation ⋮ Approximation algorithms and hardness results for the clique packing problem ⋮ Approximation algorithms and hardness results for the clique packing problem ⋮ A modified greedy algorithm for dispersively weighted 3-set cover ⋮ A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem ⋮ Dual parameterization of weighted coloring ⋮ The maximum \(f\)-depth spanning tree problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Approximation results for the minimum graph coloring problem
- A modified greedy heuristic for the set covering problem with improved worst case bound
- Maximizing the number of unused colors in the vertex coloring problem
- 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
This page was built for publication: Approximating k-set cover and complementary graph coloring
