文章基本信息

标题：On Approximating Degree-Bounded Network Design Problems
本地全文：下载
作者：Xiangyu Guo ; Guy Kortsarz ; Bundit Laekhanukit 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：176
页码：39:1-39:21
DOI：10.4230/LIPIcs.APPROX/RANDOM.2020.39
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 âS V, we need to output a minimum-cost arborescence in G that contains an rrightarrow t path for every t â^^ K. Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial 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 Degree-Bounded Directed Steiner Tree (DB-DST) 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 quasi-polynomial 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 non-trivial result for the problem. While our cost-guarantee 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 Degree-Bounded Group Steiner Tree problem on trees (DB-GST-T). 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 DB-GST-T.
关键词：Directed Steiner Tree; Group Steiner Tree; degree-bounded