Guo, Xiangyu ;
Kortsarz, Guy ;
Laekhanukit, Bundit ;
Li, Shi ;
Vaz, Daniel ;
Xian, Jiayi
On Approximating DegreeBounded Network Design Problems
Abstract
Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph G = (V, E) with edge costs c ∈ ℝ_{≥ 0}^E, a root r ∈ V and k terminals K ⊆ V, we need to output a minimumcost arborescence in G that contains an rrightarrow t path for every t ∈ K. Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasipolynomial time O(log²k/log log k)approximation algorithms for the problem, which are tight under popular complexity assumptions.
In this paper, we consider the more general DegreeBounded Directed Steiner Tree (DBDST) problem, where we are additionally given a degree bound d_v on each vertex v ∈ V, and we require that every vertex v in the output tree has at most d_v children. We give a quasipolynomial time (O(log n log k), O(log² n))bicriteria approximation: The algorithm produces a solution with cost at most O(log nlog k) times the cost of the optimum solution that violates the degree constraints by at most a factor of O(log²n). This is the first nontrivial result for the problem.
While our costguarantee is nearly optimal, the degree violation factor of O(log²n) is an O(log n)factor away from the approximation lower bound of Ω(log n) from the Set Cover hardness. The hardness result holds even on the special case of the DegreeBounded Group Steiner Tree problem on trees (DBGSTT). With the hope of closing the gap, we study the question of whether the degree violation factor can be made tight for this special case. We answer the question in the affirmative by giving an (O(log nlog k), O(log n))bicriteria approximation algorithm for DBGSTT.
BibTeX  Entry
@InProceedings{guo_et_al:LIPIcs:2020:12642,
author = {Xiangyu Guo and Guy Kortsarz and Bundit Laekhanukit and Shi Li and Daniel Vaz and Jiayi Xian},
title = {{On Approximating DegreeBounded Network Design Problems}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {39:139:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12642},
URN = {urn:nbn:de:0030drops126420},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.39},
annote = {Keywords: Directed Steiner Tree, Group Steiner Tree, degreebounded}
}
11.08.2020
Keywords: 

Directed Steiner Tree, Group Steiner Tree, degreebounded 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Issue date: 

2020 
Date of publication: 

11.08.2020 