In the classical Steiner tree problem, given an undirected, connected graph G = (V , E) with non-negative edge costs and a set of terminalsT ⊆ V , the objective is to find a minimum-cost tree E ⊆ E that spans the terminals. The problem is APX-hard; the best-known approximation algorithm has a ratio of ρ = ln(4) + ε < 1.39. In this article, we study a natural generalization, the multi-level Steiner tree (MLST) problem: Given a nested sequence of terminalsT ⊂ · · · ⊂ T 1 ⊆ V , compute nested trees E ⊆ · · · ⊆ E 1 ⊆ 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 ( )-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 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 several integer linear programming 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 = 100 levels, which is sufficient for most applications, such as network visualization or designing multi-level infrastructure. Let G = (V , E) be an undirected, connected graph with positive edge costs c : E → R + , and let T ⊆ V be a set of vertices called terminals. A Steiner tree is a tree in G that spans T . The network (graph) Steiner tree problem (ST) is to find a minimum-cost Steiner tree E ⊆ E, where the cost of E is c (E ) = e ∈E c (e). ST is one of Karp's initial NP-hard problems [13] ; see also a survey [22] , an online compendium [12] , and a textbook [19] . Due to its practical importance in many domains, there is a long history of exact and approximation algorithms for the problem. The classical 2-approximation algorithm for ST [11] uses the metric closure of G, i.e., the complete edge-weighted graph G * with vertex set T in which, for every edge uv, the cost of uv equals the length of a shortest u-v path in G. A minimum spanning tree of G * corresponds to a 2-approximate Steiner tree in G. Currently, the last in a long list of improvements is the LP-based approximation algorithm of Byrka et al. [6] , which has a ratio of ln(4) + ε < 1.39. Their algorithm uses a new iterative randomized rounding technique. Note that ST is APX-hard [4]; more concretely, it is NP-hard to approximate the problem within a factor of 96/95 [8] . This is in contrast to the geometric variant of the problem, where terminals correspond to points in the Euclidean or rectilinear plane. Both variants admit polynomial-time approximation schemes (PTAS) [1, 16] , while this is not true for the general metric case [4] . In this article, we consider the natural generalization of ST where the terminals appear on "levels" (or "grades of service") and must be connected by edges of appropriate levels. We propose new approximation algorithms and compare them to existing ones both theoretically and experimentally. Definition 1.1 (Multi-level Steiner Tree (MLST) Problem). Given a connected, undirected graph G = (V , E) with edge weights c : E → R + and nested terminal sets T ⊂ · · · ⊂ T 1 ⊆ V , a multilevel Steiner tree consists of nested edge sets E ⊆ · · · ⊆ E 1 ⊆ E such that E i spans T i for all 1 ≤ i ≤ . The cost of an MLST is defined by the sum of the edge weights across all levels, i=1 c (E i ) = i=1 e ∈E i c (e). The MLST problem is to find an MLST E OPT, ⊆ · · · ⊆ E OPT,1 ⊆ E with minimum cost. The above LP has + 1 variables and 2 −1 + 2 constraints. Each subset Q ∈ {1, 2, . . . , } with 1 ∈ Q corresponds to one constraint. Lemma 2.6. The system of 2 −1 inequalities can be expressed in matrix form as t · 1 2 −1 ×1 ≤ M y,
These approaches are ( +1 2 )ρ-and ρ-approximations, respectively REF .
Multi-level Steiner Trees
JEAL
Computer Science Mathematics