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

  • $\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 '13 at 17:23
  • 3
    $\begingroup$ It seems like a generalized 1-median problem. $\endgroup$ – Suresh Venkat Jan 2 '13 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 '13 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 '13 at 6:53

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.

| cite | improve this answer | |
  • 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 '13 at 2:02

Your Answer

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

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