<p>It is called p-Median and is known to be NP-hard.
Refer to the following paper for more info: </p>

<blockquote>
  <p>O. Kariv and S. Hakimi, “<a href="http://www.jstor.org/discover/10.2307/2100911" rel="nofollow">An Algorithmic Approach to Network Location
  Problems. II: The p-MEDIANS</a>,” <em>SIAM Journal on Applied Mathematics</em>,
  vol. 37, no. 3, pp. 539–560, December 1979.</p>
</blockquote>

CC BY-SA 3.0
2013-01-06T02:02:57.710Z
That seems to be about the special case where the sets $P_i$ consist of every one of the $\binom{n}{p}$ subsets of $p$ points of the input, and the NP-hardness result in that paper requires $p$ to be non-constant. So this doesn't appear to say much about the hardness of the problem asked here in which the $P_i$ are specified, because expanding out all of the $p$-subsets into an explicit list of sets is not a polynomial-time reduction.
David Eppstein
CC BY-SA 3.0
2013-01-05T23:24:23.320Z
2013-01-05T23:24:23.320Z
Ali
<p>In a paper I am reviewing, the authors define the following problem and construct an algorithm. They give no further references and I suspect it has appeared somewhere in the literature before.</p>

<p>Let $P_1,\ldots,P_n$ be sets of points in a space with a metric $d$. Define the distance to a set as 
    $$\operatorname{dist}(x, P_i) = \min\{ d(x,p) \,|\, x \in P_i\}.$$
The problem is to compute
    $$\min_x \sum_{i=1}^n \operatorname{dist}(x, P_i).$$
What is the name of this problem? Has it been discussed in the literature? What if $d(x,P_i) = ||x - P_i||_2?$</p>

CC BY-SA 3.0
2013-01-02T17:23:07.540Z
I don't know of any references to that specific formula, but wouldn't this be covered under optimization/minimization problems?
Ronny
CC BY-SA 3.0
2013-01-02T17:42:27.143Z
It seems like a generalized 1-median problem.
Suresh Venkat
CC BY-SA 3.0
2013-01-02T18:57:29.773Z
The 1-median problem would be to minimize sum_i sum_{p in P_i} d(x, p), right? Has the generalized version appeared anywhere?
Ben
CC BY-SA 3.0
2013-01-06T06:53:13.760Z
Not that I'm aware of. Of course it inherits all of the hardness of the 1-median since all the sets can be singletons. It should also admit the 2-approximation that comes from choosing one of the input points as the center.
Suresh Venkat
<reference-request><cg.comp-geom>
Finding the closest point to a sets of discrete points
Ben
# Finding the closest point to a sets of discrete points

(Asked by: username_0 on 2013-01-02)

In a paper I am reviewing, the authors define the following problem and construct an algorithm. They give no further references and I suspect it has appeared somewhere in the literature before.

Let $P\_1,\ldots,P\_n$ be sets of points in a space with a metric $d$. Define the distance to a set as
$$\operatorname{dist}(x, P\_i) = \min\{ d(x,p) \,|\, x \in P\_i\}.$$
The problem is to compute
$$\min\_x \sum\_{i=1}^n \operatorname{dist}(x, P\_i).$$
What is the name of this problem? Has it been discussed in the literature? What if $d(x,P\_i) = ||x - P\_i||\_2?$

**Tags:** reference-request, cg.comp-geom

> **Comments:**
> **username_1**: I don't know of any references to that specific formula, but wouldn't this be covered under optimization/minimization problems?  
> **username_2**: It seems like a generalized 1-median problem.  
> **username_0**: The 1-median problem would be to minimize sum_i sum_{p in P_i} d(x, p), right? Has the generalized version appeared anywhere?  
> **username_2**: Not that I'm aware of. Of course it inherits all of the hardness of the 1-median since all the sets can be singletons. It should also admit the 2-approximation that comes from choosing one of the input points as the center.  

---

## 1 answers

### Answer by username_3 on 2013-01-05. Score: 4

It is called p-Median and is known to be NP-hard.
Refer to the following paper for more info:

> O. Kariv and S. Hakimi, “[An Algorithmic Approach to Network Location
> Problems. II: The p-MEDIANS](http://www.jstor.org/discover/10.2307/2100911),” *SIAM Journal on Applied Mathematics*,
> vol. 37, no. 3, pp. 539–560, December 1979.

> **Comments:**
> **username_4**: That seems to be about the special case where the sets $P_i$ consist of every one of the $\binom{n}{p}$ subsets of $p$ points of the input, and the NP-hardness result in that paper requires $p$ to be non-constant. So this doesn't appear to say much about the hardness of the problem asked here in which the $P_i$ are specified, because expanding out all of the $p$-subsets into an explicit list of sets is not a polynomial-time reduction.  

---

