Euclidean Steiner Forest Problem

• INSTANCE: Finite set of $k$ terminal pairs $S = \{(s_1,t_1), ..., (s_k, t_k)\} \subset \mathbb{R}^2$ .

• SOLUTION: A forest $F$ such that for all $1\leq j\leq k$ , vertices $s_j$ and $t_j$ are contained in the same connected component of $F, F \subset \mathbb{R}^2$ .

• COST FUNCTION: The Euclidean length $d_2(F)= \displaystyle \sum_{\{u,v\} \in F}{\vert\vert u - v\vert\vert}_2$ of $F$ , where ${\vert\vert\cdot\vert\vert}_2$ denotes the Euclidean Norm in $\mathbb{R}^2$ .

• OBJECTIVE: Minimize

• Approx.: Admits a PTAS [20].

• 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].