On approximating degree-bounded network design problems

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 ∈ RE0, a root r ∈ V and k terminals K ⊆ V, we need to output a 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(log2 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 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 n log k), O(log2 n))-bicriteria approximation: The algorithm produces a solution with cost at most O(log n log k) times the cost of the optimum solution that violates the degree constraints by at most a factor of O(log2 n). This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of O(log2 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 n log k), O(log n))-bicriteria approximation algorithm for DB-GST-T.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020
EditorsJaroslaw Byrka, Raghu Meka
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771641
DOIs
StatePublished - Aug 1 2020
Event23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020 - Virtual, Online, United States
Duration: Aug 17 2020Aug 19 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume176
ISSN (Print)1868-8969

Conference

Conference23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020
Country/TerritoryUnited States
CityVirtual, Online
Period8/17/208/19/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Degree-bounded
  • Directed Steiner Tree
  • Group Steiner Tree

Fingerprint

Dive into the research topics of 'On approximating degree-bounded network design problems'. Together they form a unique fingerprint.

Cite this