most recent 30 from http://mathoverflow.net 2013-05-21T19:10:18Z http://mathoverflow.net/feeds/question/49989 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49989/algorithm-for-k-medians-in-a-convex-polygon Garrett Baird 2010-12-20T18:38:38Z 2010-12-25T23:15:58Z

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

http://mathoverflow.net/questions/49989/algorithm-for-k-medians-in-a-convex-polygon/50109#50109 Garrett Baird 2010-12-22T00:25:29Z 2010-12-22T00:25:29Z

<p>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).</p> <p>EDIT: Sorry folks, looks like I replied in the wrong place.</p>

http://mathoverflow.net/questions/49989/algorithm-for-k-medians-in-a-convex-polygon/50146#50146 Suresh Venkat 2010-12-22T10:11:57Z 2010-12-22T10:11:57Z

<p>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 <a href="http://arxiv.org/abs/cs/0310027" rel="nofollow">2003 paper by Fekete, Mitchell and Beurer</a>. 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. </p> <p>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. </p>

http://mathoverflow.net/questions/49989/algorithm-for-k-medians-in-a-convex-polygon/50340#50340 Joseph O'Rourke 2010-12-25T14:34:36Z 2010-12-25T14:34:36Z

<p>Following Suresh's lead, this problem is known as the <em>multisource Weber problem</em>, and searching that key phrase turns up several papers in the operations research literature. For example:</p> <p>"<a href="http://or.journal.informs.org/cgi/content/abstract/48/3/444" rel="nofollow">Improvement and Comparison of Heuristics for Solving the Uncapacitated Multisource Weber Problem</a>," <em>Operations Research</em>, Vol. 48, No. 3, May-June 2000, pp. 444-460.</p> <p>"<a href="http://www.jstor.org/pss/4101968" rel="nofollow">The Multi-Source Weber Problem with Constant Opening Cost</a>," <em>Journal of Operations Research Society</em>, 2004, 55, 640-6.</p>

http://mathoverflow.net/questions/49989/algorithm-for-k-medians-in-a-convex-polygon/50381#50381 John Gunnar Carlsson 2010-12-25T23:15:58Z 2010-12-25T23:15:58Z

<p>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</p> <p><a href="http://www.tc.umn.edu/~jcarlsso/fermat-weber.pdf" rel="nofollow">http://www.tc.umn.edu/~jcarlsso/fermat-weber.pdf</a></p> <p>if anyone is interested.</p>