The following problem is a special case of k-medians. Is it NP-hard? Is it in P?

Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$.

Output: a set $S$ containing $k$ of the given points, of minimum cost, defined as $\sum_i d((x_i,y_i), S)$, where $$ d((x_i, y_i), S) = \min\big(y_i, ~\min\{ y_i - y_j : j \in S \,\wedge\, y_j \le y_i \,\wedge\,|x_i - x_j| \le 1 \}\big).$$

I think of this as each point "falling" vertically just until it either (a) reaches the x-axis, or (b) is aligned horizontally with, and at distance at most 1 from, one of the $k$ chosen points. The goal is to choose the $k$ points to minimize the total distance fallen by the remaining points, as shown below. (The input is on the left, a solution with $k=3$ is on the right. The cost of the solution is the total length of the dashed vertical lines.)

$~~~~~~~~~$enter image description here

$~~~~~~~~~~~~~~~~~~~~~~$ input $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$ solution with $k=3$

  • 1
    $\begingroup$ Interesting. My first thought was to use dynamic programming on the x-ordered points but thar doesn't seem to work: the cluster centers can all be assumed to have the same y coordinate as an input and an x-coordinate one off from an input, but it may be necessary to keep track of large sets of cluster centers that are all active at the same x coordinate. $\endgroup$ – David Eppstein May 4 '15 at 7:39
  • $\begingroup$ @DavidEppstein, Agreed. Note that the $k$ chosen points are from the input points. I'd also be interested in the variant where each point is either "red" or "blue", the $k$ chosen points must be blue, and in the cost the sum is over the red points only. $\endgroup$ – Neal Young May 6 '15 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.