# 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

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

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

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.

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

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

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

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 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 ... 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 Though unrelated, this lecture note contains a potential function based neat proof of the$O(\log k)$-approximation. 1 For the non-metric$k$-median problem, we can show a stronger inapproximability result than$O(\log n)$. The following is a stronger claim: Main Claim: The non-metric$k$-median problem can not be approximated to any factor better than$n^{c}$, for any constant$c>0$. Proof: The proof follows from the reduction from the hardness of the max$k$coverage ... 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 (...

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