On approximating degree-bounded network design problems
From MaRDI portal
Publication:2134742
DOI10.1007/s00453-022-00924-0OpenAlexW4206900033MaRDI QIDQ2134742
Shi Li, Guy Kortsarz, Jiayi Xian, Daniel Vaz, Xiangyu Guo, Bundit Laekhanukit
Publication date: 3 May 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.11404
Cites Work
- Unnamed Item
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- The minimum degree group Steiner problem
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- Survivable Network Design with Degree or Order Constraints
- Polylogarithmic inapproximability
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Online Degree-Bounded Steiner Network Design
- Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering
- Approximation Algorithms for Directed Steiner Problems
- Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- O (log 2 k / log log k )-approximation algorithm for directed Steiner tree
- Many birds with one stone
- Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
- Additive Approximation for Bounded Degree Survivable Network Design
- Linear Programming Hierarchies Suffice for Directed Steiner Tree
- Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
- A tight bound on approximating arbitrary metrics by tree metrics
