  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 $\rho = \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.
