On Approximating Degree-Bounded Network Design Problems

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

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

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∈R≥0E, a root r∈ V and k terminals K⊆ V, we need to output the minimum-cost arborescence in G that contains an r→ t path for every t∈ K. Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial time O(log 2k/ 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 dv on each vertex v∈ V, and we require that every vertex v in the output tree has at most dv children. We give a quasi-polynomial time (O(log nlog k) , O(log 2n)) -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 2n). This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of O(log 2n) 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.

שפה מקוריתאנגלית
מספר המאמר5
עמודים (מ-עד)1252-1278
מספר עמודים27
כתב עתAlgorithmica
כרך84
מספר גיליון5
תאריך מקוון מוקדם24 ינו׳ 2022
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - מאי 2022
פורסם באופן חיצוניכן

הערה ביבליוגרפית

Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On Approximating Degree-Bounded Network Design Problems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי