4
$\begingroup$

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?$

Improve this question
$\endgroup$
4
  • $\begingroup$ I don't know of any references to that specific formula, but wouldn't this be covered under optimization/minimization problems? $\endgroup$
    – Ronny
    Jan 2, 2013 at 17:23
  • 3
    $\begingroup$ It seems like a generalized 1-median problem. $\endgroup$
    – Suresh Venkat
    Jan 2, 2013 at 17:42
  • $\begingroup$ 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? $\endgroup$
    – Ben
    Jan 2, 2013 at 18:57
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Jan 6, 2013 at 6:53

1 Answer 1

Reset to default
4
$\begingroup$

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,” SIAM Journal on Applied Mathematics, vol. 37, no. 3, pp. 539–560, December 1979.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Jan 6, 2013 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.