Multi-Level Steiner Trees
Reyan Ahmed Angelini, Patrizio
Faryad Darabi Sahneh Alon Efrat David Glickenstein Martin Gronemann Niklas Heinsohn Stephen G. Kobourov Richard Spence Joseph Watkins
Reyan Ahmed
Faryad Darabi Sahneh
Alon Efrat
David Glickenstein
Martin Gronemann
Niklas Heinsohn
Stephen G. Kobourov
Richard Spence
Joseph Watkins
Citations
Altmetric:
Abstract
In the classical Steiner tree problem, given an undirected, connected graph $G=(V,E)$ with non-negative edge costs and a set of \emph{terminals} $T\subseteq V$, the objective is to find a minimum-cost tree $E' \subseteq E$ that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of $ρ= \ln(4)+\varepsilon < 1.39$. In this paper, we study a natural generalization, the \emph{multi-level Steiner tree} (MLST) problem: given a nested sequence of terminals $T_{\ell} \subset \dots \subset T_1 \subseteq V$, compute nested trees $E_{\ell}\subseteq \dots \subseteq E_1\subseteq E$ that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names including Multi-level Network Design, Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two simple $O(\ell)$-approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most $2\ell$ Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present various integer linear programming (ILP) formulations for the MLST problem, and compare their running times on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to $\ell=100$ levels, which is sufficient for most applications such as network visualization or designing multi-level infrastructure.
Description
Date
2019
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Keywords
Theory of computation, Sparsification and spanners, Approximation algorithms, Multi-level graph representation
Citation
Ahmed, Reyan, Patrizio Angelini, Faryad Darabi Sahneh, et al. “Multi-Level Steiner Trees.” ACM Journal of Experimental Algorithmics 24: 2.5:1-2.5:22. 2019.