tag:blogger.com,1999:blog-6555947.post429446630961949282..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: NP hardness of Euclidean k-median clusteringSuresh Venkatasubramanianhttps://plus.google.com/112165457714968997350noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-6555947.post-43514607141749922232009-10-17T09:57:23.546-06:002009-10-17T09:57:23.546-06:00I am wondering what is known for the k-median prob...I am wondering what is known for the k-median problem in hamming distance space. Any good solutions?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-25477274475574601402007-09-06T05:50:00.000-06:002007-09-06T05:50:00.000-06:00I thought that "designated point" meant that the c...I thought that "designated point" meant that the cluster median was to be selected among the given points. Megiddo and Supowit proof the version where the medians are freely selectable from real plane. <BR/><BR/>The version where the medians must be selected from the given points (with Euclidean metrics) was proved to be NP-complete by Papadimitriou [Worst-Case and Probabilistic Analysis of a Geometric Location Problem, SIAM J. Comput. 10(3), 1989].<BR/><BR/>Anyhow, it's quite annoying when the same name refers to two different problems. I've seen somebody using "Geometric k-Median" to refer to the Megiddo and Supowit's version, but I don't know do I like it. Opinions?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-83858889725697120982007-09-06T00:31:00.000-06:002007-09-06T00:31:00.000-06:00ah ! and I've even read this paper before. Yes, th...ah ! and I've even read this paper before. <BR/><BR/>Yes, that indeed is a proof. Specifically they show that k-median in the plane is NP-hard, by a very complicated reduction from 3SAT. <BR/><BR/>thanks !Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-72094100265659750882007-09-06T00:16:00.000-06:002007-09-06T00:16:00.000-06:00If I am not mistaken, the following paper shows th...If I am not mistaken, the following paper shows that NP-Hardness of the k-median problem under Eucledean metric.<BR/><BR/>N. Megiddo and K. Supowit.<BR/>On the complexity of some common geometric location problems.<BR/>SIAM J Computing, 13(1), 1984.Venkat Chakaravarthywww.cs.wisc.edu/~venkatnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-16577755518159345382007-09-04T06:25:00.000-06:002007-09-04T06:25:00.000-06:00A quick comment: the Arora-Raghavan-Rao PTAS holds...A quick comment: the Arora-Raghavan-Rao PTAS holds only for *low-dimensional* Euclidean metrics. Specifically, the running time of the algorithm is doubly exponential in d. <BR/><BR/>As far as the hardness goes, it is known that the doubly exponential dependence is (likely) necessary for a PTAS, *if* your medians must come from a given set (the "discrete median" case). This follows from a combination of papers, incl. Trevisan'97, see comments in Guruswami-Indyk, SODA'03. <BR/>So in particular, it is known that there is no PTAS for the discrete k-median in general Euclidean spaces (unless something strange happens)<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-90151850611305601042007-09-03T22:45:00.000-06:002007-09-03T22:45:00.000-06:00If by k-variance you mean minimizing the sum of sq...If by k-variance you mean minimizing the sum of squares of distances of intracluster pairs, then there's a paper by Schulman from STOC 2000 that's relevant here. <BR/><BR/>http://portal.acm.org/citation.cfm?doid=335305.335373Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-32192967304676302242007-09-03T21:16:00.000-06:002007-09-03T21:16:00.000-06:00WoW !! what a coincidence ? I was trying to find a...WoW !! what a coincidence ? I was trying to find an answer to this exact question over this long-weekend. I could not get any NP-hardness proof after three days of crazy googling and acm-search. Thanks for asking this question.<BR/><BR/>I have a related question. What exactly is <I>the k-variance problem</I> ? I came across couple of different definitions. Is it's complexity open ? Are there any known results for k-variance on euclidean plane.Shiva Kintalihttp://www.blogger.com/profile/07853545928906483737noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-69213616650119930422007-09-03T19:16:00.000-06:002007-09-03T19:16:00.000-06:00The best known approximation fork-median in genera...The best known approximation for<BR/>k-median in general metric spaces<BR/>is 3+\eps due to a local search<BR/>algorithm of Arya etal.Chandrahttp://www.blogger.com/profile/00057069075567569157noreply@blogger.com