
Kruskalbased approximation algorithm for the multilevel Steiner tree problem
We study the multilevel Steiner tree problem: a generalization of the S...
read it

Computing VertexWeighted MultiLevel Steiner Trees
In the classical vertexweighted Steiner tree problem (VST), one is give...
read it

On the minimum spanning tree problem in imprecise setup
In this article, we study the Euclidean minimum spanning tree problem in...
read it

Approximation algorithms for priority Steiner tree problems
In the Priority Steiner Tree (PST) problem, we are given an undirected g...
read it

A PrimalDual based Distributed Approximation Algorithm for Prize Collecting Steiner Tree
Constructing a steiner tree of a graph is a fundamental problem in many ...
read it

Approximation algorithms and an integer program for multilevel graph spanners
Given a weighted graph G(V,E) and t > 1, a subgraph H is a tspanner of...
read it

A General Framework for Multilevel Subsetwise Graph Sparsifiers
Given an undirected weighted graph $G(V,E)$, a subsetwise sparsifier ove...
read it
MultiLevel Steiner Trees
In the classical Steiner tree problem, one is given an undirected, connected graph G=(V,E) with nonnegative edge costs and a set T ⊆ V, the terminals. The objective is to find a minimumcost edge set E' ⊆ E that spans the terminals. The problem is APXhard [Bern & Plassman, IPL 1989]; the best known approximation algorithm has a ratio of ρ = (4)+ε < 1.39 [Byrka et al., J. ACM 2013]. In this paper, we study a natural generalization, the multilevel Steiner tree (MLST) problem: given a nested sequence of terminals T_1 ⊂...⊂ T_k ⊆ V, compute nested edge sets E_1 ⊆...⊆ E_k ⊆ E that span the corresponding terminal sets with minimum total cost. (Note that, for ℓ=1,...,k, edges in E_ℓ contribute (kℓ+1)fold to this cost). The MLST problem and variants thereof have been studied under names such as QualityofService Multicast tree, GradeofService Steiner tree, MultiTier tree, etc. Several approximation results are known. We first present two natural heuristics with approximation factor O(k). Based on these, we introduce a composite algorithm that requires 2^k Steiner tree computations. We determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio and needs at most 2k Steiner tree computations. We compare five algorithms experimentally on several classes of graphs using ErdősRényi, random geometric, WattsStrogatz, and BarabásiAlbert network generation models for varying V, k, and terminal selection methods. We also implemented an integer linear program for MLST to provide ground truth. Our combined algorithm outperforms the others both in theory and in practice when the number of levels is up to k < 22.
READ FULL TEXT
Comments
There are no comments yet.