6
$\begingroup$

Are there any known approximation algorithms or exact solution schemes for the k-medians problem in a convex polygon? That is, placing a collection of points $p_1,\dots,p_k \subset \mathbb{R}^2$ in a convex polygon $C$ so as to minimize $$\iint_C \min_i \|x-p_i\| dx$$

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Nice question! For the ellipse $x^2/a^2 + y^2/b^2 = 1$ and $k=2$, the points are not at the foci. For $a=2$, $b=1$, about $(\pm 0.85,0)$. $\endgroup$
    – Joseph O'Rourke
    Dec 21, 2010 at 0:52
  • $\begingroup$ Is there even a nice algorithm for k=1 ? $\endgroup$
    – HenrikRüping
    Dec 21, 2010 at 14:00
  • $\begingroup$ @Henrik: Good question! Not generally at the center of gravity... $\endgroup$
    – Joseph O'Rourke
    Dec 21, 2010 at 19:32
  • 1
    $\begingroup$ For $k=1$, the functional is convex and, if you have any way to compute it in a reasonable time (say, by partitioning into triangles, or so), you can use the standard gradient descent methods. All that fails miserably for larger $k$. The minimum is no longer unique (say for 2 points in an equilateral triangle) and everything becomes a mess. What range of $k$ are you interested in? $\endgroup$
    – fedja
    Dec 22, 2010 at 0:18
  • $\begingroup$ @Joseph: If you square the distance and $k=1$, then it's the center of gravity. $\endgroup$
    – Michael Hardy
    Dec 22, 2010 at 22:30

4 Answers 4

Reset to default
5
$\begingroup$

The problem you're asking about (for $k=1$) is called the continuous Fermat-Weber problem. The primary work on this that I'm aware of is the 2003 paper by Fekete, Mitchell and Beurer. While they examine this problem, they focus on the $\ell_1$ plane (the analytics are easier) and also pay more attention to the $k=1$ case, while also discussing some hardness results.

My $.02$ is that there should be some way of getting an approximation by discretizing the region - it's not clear to me that convexity helps a lot though.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Why? I agree that when the function is just barely convex, you may have headaches with the descent methods but this one has a good a priori bound for the second derivative in every direction, so the most naiive implementations require just logarithm of the precision steps. $\endgroup$
    – fedja
    Dec 22, 2010 at 18:58
  • $\begingroup$ I was referring to convexity in the region, not the function. $\endgroup$
    – Suresh Venkat
    Dec 23, 2010 at 17:21
4
$\begingroup$

A while ago I wrote, but never published, an approximation algorithm for this problem. Using some new results and updating the citations, it looks like I can get the approximation constant down to 9.026 (assuming I didn't make any mistakes). It's not clear to me if that's publication-worthy, but I uploaded a draft to

http://www.tc.umn.edu/~jcarlsso/fermat-weber.pdf

if anyone is interested.

Improve this answer
$\endgroup$
4
1
$\begingroup$

Following Suresh's lead, this problem is known as the multisource Weber problem, and searching that key phrase turns up several papers in the operations research literature. For example:

"Improvement and Comparison of Heuristics for Solving the Uncapacitated Multisource Weber Problem," Operations Research, Vol. 48, No. 3, May-June 2000, pp. 444-460.

"The Multi-Source Weber Problem with Constant Opening Cost," Journal of Operations Research Society, 2004, 55, 640-6.

Improve this answer
$\endgroup$
2
  • $\begingroup$ juat a clarification though: it seems to me that both links still refer to the discrete setting (i.e the k-median) where the number of "users" is finite. Aside: I didn't know that there's this entire subfield devoted to the k-median under this name. certainly the theoryCS literature doesn't directly mention it, and the OR community appears to return the favor :) $\endgroup$
    – Suresh Venkat
    Dec 25, 2010 at 17:58
  • $\begingroup$ @Suresh: Yes, you are right, these references are to the discrete version. And it is quite interesting that the two communities are apparently unaware of one another! Maybe this MO question will serve as a start toward bridging that gap. $\endgroup$
    – Joseph O'Rourke
    Dec 25, 2010 at 18:41
0
$\begingroup$

There's no particular range of $k$ that I'm interested in; actually, I'm just curious if there's already a well-known PTAS or an approximation algorithm, and whether that's considered an "interesting" problem in the geometry community. It seems that the problem becomes easier as $k$ becomes really big, since you just want to scatter the points in as uniform a fashion as possible (like the centers of a hexagonal tiling or something like that).

EDIT: Sorry folks, looks like I replied in the wrong place.

Improve this answer
$\endgroup$
1

Your Answer

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

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