Bounded Skew Tree Problem

• INSTANCE: Metric space $(M,d)$ , set of sinks $S \subseteq M$ , edge costs $cost: E \rightarrow\mathbb{R}^+$ , bound$b$ .
• SOLUTION: A stretched tree $T=(V_T, E_T, \pi, c)$ consisting of an arborescence $(V_T,E_T)$ , a mapping $\pi: V_T \rightarrow M$ such that $\pi$ is a one-to-one mapping between the leaves of $T$ and $S$ and a cost function $c\colon E_T\to \mathbb{R}_+$ such that for every edge $(u,v)$ of $T$ , $c(u,v)\geq d(\pi(u),\pi(v))$ and furthermore, for each pair $P,P'$ of root-to-leaf paths in $T$ , $\vert c(P)-c(P')\vert\leq b$
• COST FUNCTION: $\sum_{(u,v)\in E}cost(u,v)$
• OBJECTIVE: Minimize.
• Approx.: Approximable within approximation ratio 14 when the root is not fixed as a part of the instance [110]. Approximable within $16.86$ when the root is given as part of the input [28].
• Hardness: NP-hard [28]. Also NP-hard in the two-dimensional rectilinear case [110].