Welcome to MathOverflow

Question

6

1

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

flag	asked Dec 20 2010 at 18:38 Garrett Baird 61●1

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 2010 at 0:52

Is there even a nice algorithm for k=1 ? – HenrikRüping Dec 21 2010 at 14:00

@Henrik: Good question! Not generally at the center of gravity... – Joseph O'Rourke Dec 21 2010 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 2010 at 0:18

@Joseph: If you square the distance and $k=1$, then it's the center of gravity. – Michael Hardy Dec 22 2010 at 22:30

show 6 more comments

Garrett Baird · Answer 1 · 2010-12-22 00:25:29Z UTC

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.

Suresh Venkat · Answer 2 · 2010-12-22 10:11:57Z UTC

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.

Joseph O'Rourke · Answer 3 · 2010-12-25 14:34:36Z UTC

1

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.

answered Dec 25 2010 at 14:34

Joseph O'Rourke
43.2k●1●49●214

	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 2010 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 2010 at 18:41

John Gunnar Carlsson · Answer 4 · 2010-12-25 23:15:58Z UTC

4

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.

answered Dec 25 2010 at 23:15

John Gunnar Carlsson
753●2●9

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

Algorithm for k-medians in a convex polygon

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

4 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.