<p>The following problem is a special case of k-medians.  Is it NP-hard?  Is it in P?</p>
<p><strong>Input</strong>: <span class="math-container">$n$</span> points <span class="math-container">$(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$</span> with each <span class="math-container">$y_i \ge 0$</span>, and an integer <span class="math-container">$k$</span>.</p>
<p><strong>Output</strong>: a set <span class="math-container">$S$</span> containing <span class="math-container">$k$</span> of the given points, of minimum <em>cost</em>, defined as <span class="math-container">$\sum_i d((x_i,y_i), S)$</span>, where
<span class="math-container">$$ 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).$$</span></p>
<p>I think of this as each point &quot;falling&quot; 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 <span class="math-container">$k$</span> chosen points.  The goal is to choose the <span class="math-container">$k$</span> points to minimize the total distance fallen by the remaining points, as shown below.  (The input is on the left, a solution with <span class="math-container">$k=3$</span> is on the right.  The cost of the solution is the total length of the dashed vertical lines.)</p>
<blockquote>
<p><span class="math-container">$~~~~~~~~~$</span><img src="https://i.sstatic.net/EMYbt.png" alt="enter image description here" /></p>
<p><span class="math-container">$~~~~~~~~~~~~~~~~~~~~~~$</span> input  <span class="math-container">$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$</span> solution with <span class="math-container">$k=3$</span></p>
</blockquote>

CC BY-SA 3.0
2015-05-04T07:39:32.973Z
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.
David Eppstein
CC BY-SA 3.0
2015-05-06T16:34:04.090Z
@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.
Neal Young
CC BY-SA 4.0
2021-06-16T21:15:57.707Z
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.
Chandra Chekuri
CC BY-SA 4.0
2022-02-22T00:49:32.757Z
@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?
ErroR
<np-hardness><polynomial-time><set-cover><clustering><dynamic-programming>
a geometric variant of k-medians. NP-hard or in P?
Neal Young
# a geometric variant of k-medians. NP-hard or in P?

(Asked by: username_0 on 2015-05-04)

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](https://i.sstatic.net/EMYbt.png)
>
> $~~~~~~~~~~~~~~~~~~~~~~$ input $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$ solution with $k=3$

**Tags:** np-hardness, polynomial-time, set-cover, clustering, dynamic-programming
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: 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.  
> **username_3**: @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?  

---

## 0 answers

