Euclidean Steiner Tree Problem

• INSTANCE: Finite set $S \subset \mathbb{R}^2$ of terminals.
• SOLUTION: A Steiner tree $T = (V_T, E_T)$ for $S$ with $S \subseteq V_T \subset \mathbb{R}^2$ .
• COST FUNCTION: The Euclidean length $d_2(T)=\displaystyle \sum_{\{u,v\} \in E_T}{\vert\vert u - v\vert\vert}_2$ of $T$ , where ${\vert\vert\cdot\vert\vert}_2$ denotes the Euclidean Norm in $\mathbb{R}^2$ .
• OBJECTIVE: Minimize
• Approx.: Admits a PTAS [7].
• Hardness: NP-hard [7].
• Comment: $d$ -dimensional version where $S\subset \mathbb{R}^d$ admits a PTAS for $d$ being constant. For $d=\log (\vert S\vert)\slash\log\log (\vert S\vert)$ the problem is APX-hard [102].