We’re rewarding the question askers & reputations are being recalculated! Read more.
10

If you insist on precise partition, then you need to compute all the balanced partitions of a set of points in the plane by a line (the optimal partition is a Voronoi partition, so the two point sets are separated by a line). Such partitions are known as $k$-sets. The fastest algorithm currently known for this work in $O(n^{4/3} \log n)$ for computing these ...


7

The problem of minimizing the sum of distances from points to cluster centers is called the $k$-median problem. In a general metric space, the $k$-median can be approximated to within a factor of $3+\epsilon$ and is $\mathsf{MAX SNP}$-hard. In Euclidean space, the problem admits a PTAS. This is a good survey and has references for the above facts.


6

Have you seen this paper by Piotr Indyk ? It's old, but it's a good one. It solves a number of problems including k-median while making only sublinear number of calls to the distance oracle. It's not exactly the model you're looking for, but it does try to reduce the number of distance invocations.


5

There may be a way to shoe horn the Johnson-Lindenstrauss theorem into this problem. Essentially, J-L states that you can project high dimensional data into lower dimensional spaces in such a way that the pairwise distances are nearly preserved. More practically, Achlioptas has a paper called Database-friendly random projections: Johnson-Lindenstrauss with ...


5

This is the geometric median problem. There is a nearly linear time algorithm based on interior point methods due to Cohen et al.: to find a $(1+\varepsilon)$-approximation their algorithm runs in time $O(nd\log^3(n/\varepsilon))$. Note that some approximation is necessary, because the optimal solution may not be rational and doesn't have to be a simple ...


5

At the risk of sounding immodest, I wrote a short survey on stream clustering a few years ago. It's a little out of date, but not overly so, and doing forward citations will get you to the recent work in the area.


4

This problem is called MIN-SUM clustering and is NP-hard. There's a paper by Bartal, Charikar and Raz from 2001 that has an approximation scheme for it: the paper also includes references to the NP-hardness result and other related results.


4

First. One can do better as far as the sampling - at least if $d$ is large - $O(\frac{kd \log k}{\epsilon} \log \frac{1}{\epsilon})$ should follow easily from relative approximations http://sarielhp.org/p/06/relative/ and combining range spaces of bounded VC dimension (if you send me email I would email you a pdf containing this combining result you need - ...


3

The edge sets whose deletion leaves a cluster graph can easily be described as a formula with one free variable (the edge set) in monadic second-order graph logic. Therefore, by an optimization version of Courcelle's theorem, the minimum cardinality set can be found in linear time for graphs of bounded treewidth, which obviously include the 2-trees. See e.g....


3

I will consider the case of non-negative weights only. As I mentioned in the comment the problem is related to the minimum k-way cut problem where the goal is to partition a given graph G into k non-trivial components to minimize the number (or weight in the weighted case) of edges crossing the partition. This is the same as maximizing the number of edges in ...


3

This problem is known as Geometric Set Cover (which deals with covering with different shapes, so unit balls are a special case). I'm unaware of any relation to $k$-means which is a clustering algorithm whose clusters are not limited in radius. The problem is known to be NP-complete for $k\geq 2$. For unit balls, this problem has a PTAS ( ($1+\epsilon$)-...


3

It seems that $Sep(u, v)$ is a vertex separator extended to graphs where $u$ and $v$ are adjacent, by ignoring their common edge. I assume the correct definition is ... vertex separator in $G$ if $\{u,v\} \notin E$ or in $G′=(V,E \setminus \{\{u,v\}\})$ otherwise. As given, the definition makes no sense. There is no point in removing $\{u, v\}$ from $...


3

I do not want to attempt a general definition of "unnatural", but I find your argument about the inherent incompatibility of the scale-invariance axiom and the richness axiom as defined in Section 2 of Kleinberg's NIPS paper. The impossibility result in Section 3 of his paper is stronger, however, and can directly address your concern. Theorem 3.1 If a ...


3

You may be interested to this survey done by a Ph.D. student, which is updated to 2009 and presents classical work on parallel clustering. The survey is full of references you may then read to delve into the gory details.


3

There's been recent work on doing clustering in the MRC model (a formal model for analyzing mapreduce computations). Specifically, you should look at the work by Bahmani et al in VLDB 2012 on k-means$||$ and earlier work by Ene et al in KDD 2011 on the same topic. These papers have some discussion of the general problem of parallelizing $k$-means, which ...


2

Since k-means minimizes the within-cluster sum of squares, the cluster centers will always be the mean of the points within that cluster. If you use a different criterion, you are basically using a different method than k-means.


1

K-means tends to create compact clusters, which means that geometrically, the distance between every two points is small. K-means can create clusters which are ball-like if you use $L_2$ norm, pyramid if you use $L_1$ and hypercubes if $L_\infty$ is used. As opposed to that there are clustering algorithms which first project the data into lower dimension (...


1

I'd recommend using a kd-tree or an R-tree. These structures automatically partition the data. A kd-tree (k-dimensional tree) is a binary tree in which every node is a point. Every non-leaf node splits the space in half along one of the axes. Points on one side of the split form the left subtree, points on another side form the right subtree. A kd-tree has ...


Only top voted, non community-wiki answers of a minimum length are eligible