Ahmed, Reyan ;
Sahneh, Faryad Darabi ;
Hamm, Keaton ;
Kobourov, Stephen ;
Spence, Richard
KruskalBased Approximation Algorithm for the MultiLevel Steiner Tree Problem
Abstract
We study the multilevel Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals T require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals u, v with priorities P(u), P(v) are connected using edges of rate min{P(u),P(v)} or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of nonproportional costs, this problem is hard to approximate with ratio c log log n, where n is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a min{2(ln T+1), 𝓁 ρ}approximation in this setting, where ρ is an approximation ratio for a heuristic solver for the Steiner tree problem and 𝓁 is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with ρ≈1.39, for example).
In this paper, we describe a natural generalization to the multilevel case of the classical (singlelevel) Steiner tree approximation algorithm based on Kruskal’s minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multilevel Steiner tree problem with nonproportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multilevel instances derived from SteinLib.
BibTeX  Entry
@InProceedings{ahmed_et_al:LIPIcs:2020:12870,
author = {Reyan Ahmed and Faryad Darabi Sahneh and Keaton Hamm and Stephen Kobourov and Richard Spence},
title = {{KruskalBased Approximation Algorithm for the MultiLevel Steiner Tree Problem}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {4:14:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12870},
URN = {urn:nbn:de:0030drops128709},
doi = {10.4230/LIPIcs.ESA.2020.4},
annote = {Keywords: multilevel, Steiner tree, approximation algorithms}
}
26.08.2020
Keywords: 

multilevel, Steiner tree, approximation algorithms 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 
Supplementary Material: 

All algorithms, implementations, the ILP solver, experimental data and analysis are available on Github at https://github.com/abureyanahmed/Kruskal_based_approximation. 