On approximating degree-bounded network design problems
type: Item
instance of: scholarly article
title: On approximating degree-bounded network design problems
author: Xiangyu Guo
author: Guy Kortsarz
author: B. Laekhanukit
author: Shi Li
author: Daniel Vaz
author: Jiayi Xian
published in: Algorithmica
publication date: 2022-05-03T00:00:00Z
full work available at URL: https://arxiv.org/abs/1907.11404
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7517135
zbMATH Keywords: group
zbMATH Keywords: Steiner
zbMATH Keywords: approximation
zbMATH Keywords: degrees
MaRDI profile type: Publication
OpenAlex ID: W4206900033
cites work: Approximation Algorithms for Directed Steiner Problems
cites work: Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering
cites work: Online Degree-Bounded Steiner Network Design
cites work: Q5002841
cites work: A tight bound on approximating arbitrary metrics by tree metrics
cites work: Linear Programming Hierarchies Suffice for Directed Steiner Tree
cites work: Approximating the Minimum-Degree Steiner Tree to within One of Optimal
cites work: A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
cites work: Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
cites work: O (log 2 k / log log k )-approximation algorithm for directed Steiner tree
cites work: Polylogarithmic inapproximability
cites work: A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
cites work: FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
cites work: Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
cites work: The minimum degree group Steiner problem
cites work: Survivable Network Design with Degree or Order Constraints
cites work: Additive Approximation for Bounded Degree Survivable Network Design
cites work: Many birds with one stone
cites work: Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
cites work: A series of approximation algorithms for the acyclic directed Steiner tree problem
DOI: 10.1007/S00453-022-00924-0
description: scientific article