Multi-Level Steiner Trees.

DOI10.4230/LIPICS.SEA.2018.15MaRDI QIDQ5140725zbMATH OpenOpenAlexFDO

Authors Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G. Kobourov, Richard Spence, Joseph C. Watkins, Alexander Wolff, Alon Efrat

Publication date 16 December 2020

Full work available at URL https://arxiv.org/abs/1804.02627

zbMATH Keywords

approximation algorithmmulti-level graph representationSteiner tree

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

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} $TsubseteqV$, the objective is to find a minimum-cost tree $E^{\prime }subseteqE$ that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of $ho=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}subsetdotssubset{T}_{1}subseteqV$, compute nested trees $E_{ell}subseteqdotssubseteq{E}_{1}subseteqE$ 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 $2ell$ 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.

Recommendations

• Multi-level Steiner trees
• Two-level hub Steiner trees
• Two-level rectilinear Steiner trees
• scientific article; zbMATH DE number 7651143
• On directed Steiner trees with multiple roots
• The multi-weighted Steiner tree problem
• Hop constrained Steiner trees with multiple root nodes
• Advances in Steiner trees
• Steiner tree problems
• Steiner tree problems

Cites work

• A comparison of Steiner tree relaxations
• Collective dynamics of `small-world' networks
• Emergence of Scaling in Random Networks
• Grade of service Steiner minimum trees in the Euclidean plane
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 970831 (Why is no real title available?)
• Improved approximation algorithms for the quality of service multicast tree problem
• Modeling and Heuristic Worst-Case Performance Analysis of the Two-Level Network Design Problem
• On the approximability of some network design problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Random Geometric Graphs
• Reducibility among combinatorial problems
• Steiner Minimal Trees
• Steiner problem in networks: A survey
• Steiner tree approximation via iterative randomized rounding
• The Multi-Tier Tree Problem
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem on graphs: inapproximability results
• The Structure and Function of Complex Networks
• Tighter Bounds for Graph Steiner Tree Approximation

Cited in

(6)

• Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems
• Multi-level Steiner trees
• The Multi-Tier Tree Problem
• scientific article; zbMATH DE number 7651143 (Why is no real title available?)
• Improved approximation algorithms for the quality of service Steiner tree problem.
• Multi-priority graph sparsification

This page was built for publication: Multi-Level Steiner Trees.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140725)