5
$\begingroup$

Suppose I am given $n$ points $p_1,\dots,p_n\in \mathbb{R}^2$, as well as two positive coefficients $a_1$ and $a_2$, and I am trying to select $n$ points $x_1,\dots,x_n$ to solve the following optimization problem, $$\min_{x_1,\dots,x_n} a_1 T(x_1,\dots,x_n) + a_2\sum_{i=1}^n \|x_i-p_i\|$$, where $T(x_1,\dots,x_n)$ is the length of a minimum spanning tree of $x_1,\dots,x_n$. Is this problem likely to be tractable (maybe within a constant factor)? Basically, the idea is that we want the $x_i$'s to be close to their respective points $p_i$, and we also want the spanning tree of the $x_i$'s to be short. In the limit as $a_1/a_2\to0$, the optimal solution has $x_i=p_i$ for all $i$, and as $a_1/a_2\to\infty$, the optimal solution has all of the $x_i$'s placed at the geometric median of the $p_i$'s. The above function is piecewise convex, in case that helps anything.

$\endgroup$
2
  • 1
    $\begingroup$ By the "minimal spanning tree" do you mean the connected tree with the vertices $x_j$ and the minimal total edge length or extra vertices are allowed (it is the same up to a factor of $2$, of course, but I am still curious). $\endgroup$
    – fedja
    Commented Aug 29, 2016 at 20:14
  • $\begingroup$ Let's say the former (vertices $x_j$), to improve whatever chances of tractability I might have. $\endgroup$ Commented Aug 29, 2016 at 20:24

0

You must log in to answer this question.