# Tag Info

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

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

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

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.

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 ... 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 Here's an example that suggests that the stronger claim in the earlier version (Lemma 5.3) is false. I've only given a cursory look at the papers, so please check this carefully to make sure I am understanding correctly, thanks. Consider a cluster$X$consisting of a rooted star: a root$r$and$n-1$nodes$v_1,v_2,\ldots, v_{n-1}$such that$d(r, v_i) = 1$... 2 Recently, I came across the following survey: Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems The authors only discuss the major results and mention some interesting open problems at the end. 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