Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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)$. –  Joseph O'Rourke Dec 21 '10 at 0:52
    
Is there even a nice algorithm for k=1 ? –  HenrikRüping Dec 21 '10 at 14:00
    
@Henrik: Good question! Not generally at the center of gravity... –  Joseph O'Rourke Dec 21 '10 at 19:32
1  
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? –  fedja Dec 22 '10 at 0:18
    
@Joseph: If you square the distance and $k=1$, then it's the center of gravity. –  Michael Hardy Dec 22 '10 at 22:30

4 Answers 4

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.

share|improve this answer
    
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. –  fedja Dec 22 '10 at 18:58
    
I was referring to convexity in the region, not the function. –  Suresh Venkat Dec 23 '10 at 17:21

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.

share|improve this answer
    
that is interesting ! thanks for sharing the draft. –  Suresh Venkat Dec 26 '10 at 9:03
    
Thanks, I already caught and fixed two typos since posting. –  John Gunnar Carlsson Dec 26 '10 at 20:50
    
Update: brought the approximation constant down to 5.02. –  John Gunnar Carlsson Jan 3 '11 at 7:25

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.

share|improve this answer
    
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 :) –  Suresh Venkat Dec 25 '10 at 17:58
    
@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. –  Joseph O'Rourke Dec 25 '10 at 18:41

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.

share|improve this answer
    
The problem seems to be that you haven't registered yet so you have multiple accounts floating around. Once you've registered, post in this meta thread to ask the moderators to merge your accounts tea.mathoverflow.net/discussion/605/merge-two-user-ids/#Item_0 –  j.c. Dec 25 '10 at 23:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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