On approximating degree-bounded network design problems

DOI10.4230/lipics.approx/random.2020.39OpenAlexW3082695672MaRDI QIDQ6084395

Guy Kortsarz, Shi Li, Daniel Vaz, Xiangyu Guo, Jiayi Xian, Bundit Laekhanukit

Publication date: 31 October 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12642/pdf/LIPIcs-APPROX39.pdf/

zbMATH Keywords

group Steiner treedirected Steiner treedegree-bounded

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• A series of approximation algorithms for the acyclic directed Steiner tree problem
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• Survivable Network Design with Degree or Order Constraints
• Polylogarithmic inapproximability
• LP-Relaxations for Tree Augmentation.
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Many birds with one stone
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• Additive Approximation for Bounded Degree Survivable Network Design
• Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal

This page was built for publication: On approximating degree-bounded network design problems