# Tree problem

Let $T$ be a tree with non-negative weighted edges and a set of $n$ leaves $L$. We are allowed to choose $k$ leaves as target points $c_1, \dots, c_k$. For a leaf $v \in L$, let $d(v, c_i)$ be the shortest path distance from $v$ to the target point $c_i$. We have to assign each leaf to some target point. For a point $c_i$ let the set of leaves assigned to it be denoted as $C_i$. The goal is to choose the locations of the target points $c_1, \dots, c_k$ and an assignment $C_1, \dots, C_k$ of leaves to them which minimizes:
$$\sum_{i = 1}^k |C_i| \sum_{v \in C_i} d(v, c_i)$$

A multiplicative $\alpha$-approximation is a solution whose objective is at most $\alpha \cdot OPT,$ where $OPT$ is the optimal cost.

**Problem 1 (easy)** For constant $k$, give a polynomial-time exact algorithm.
**Problem 2 (medium)** For arbitrary $k \le n$, give a quasipolynomial-time approximation scheme, i.e. an algorithm which for every fixed $\epsilon > 0$ achieves a multiplicative $(1+\epsilon)$-approximation in time $2^{O((\log n)^c)}$ for a constant $c > 0$.
**Problem 3 (hard)** For arbitrary $k \le n$, give a polynomial-time algorithm which achieves a multiplicative $c$-approximation for some constant $c > 0$.