16
$\begingroup$

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$

Improve this question
$\endgroup$
4
  • 2
    $\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, 2015 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, 2015 at 16:34
  • 2
    $\begingroup$ One option is to see if the natural LP relaxation is integral because of some nice structural property in the instances. If the LP is not integral it may suggest some hardness reduction. $\endgroup$
    – Chandra Chekuri
    Jun 16, 2021 at 21:15
  • $\begingroup$ @NealYoung Can I ask you a question about k-Means on the plane? My question is, there is PTAS for k-Means in the plane, after running the algorithm if we draw a grid on the clusters and each cell of the grid be a cluster, can we guarantee this idea give us a constant approximation algorithm for k-Means in the plane? $\endgroup$
    – Jut
    Feb 22, 2022 at 0:49

0

Reset to default

Your Answer

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