Two-Level Rectilinear Steiner Tree

• INSTANCE: Set of terminals $S\subset {\mathbb{R}}^2$ in the plane, partition of $S$ into $k$ subsets $S_1,\ldots , S_k$ .
• SOLUTION: Two-Level rectilinear Steiner Tree $T$ for $S$ in ${\mathbb{R}}^2$ consisting of Steiner Trees $T_i$ for $S_i$ ( $i=1,\ldots ,k$ ) and a top-level tree $T_0$ connecting the trees $T_1,\ldots , T_k$
• COST FUNCTION: $c(T_0)+\sum_{i=1}^kc(T_i)$ , where $c(\: )$ denotes the $L_1$ -length of the trees
• OBJECTIVE: Minimize.
• Approx.: Approximable within $1.63$ , based on the PTAS for Rectilinear Steiner Tree in the plane [66].

• Comment: Admits a PTAS for the case when $k$ is fixed [66].