10 votes

Bisecting a set of points into two optimal subsets

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 ...
user avatar
6 votes
Accepted

kmeans++ for arbitrary metric spaces and general potential function

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 ...
user avatar
  • 8,143
5 votes
Accepted

Finding similar vectors in subquadratic time

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 ...
user avatar
  • 201
5 votes

Centroid in $\ell_2$ distance

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 ...
user avatar
4 votes
Accepted

Determining the number of clusters using property testing algorithm

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....
user avatar
4 votes
Accepted

Approximation Ratio of Local search for $k-$center problem

Local search (with a single swap) doesn't give you a good approximation factor in the worst case for $k$-center, as illustrated by the following example. Take a simplex in $\mathbb{R}^{k-1}$, and put ...
user avatar
  • 8,143
4 votes

Cluster Edge Deletion on 2-trees

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 ...
user avatar
3 votes
Accepted

Approximating the value of k in $k$-mean clustering problem

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 ...
user avatar
  • 9,378
3 votes
Accepted

What is a minimum vertex separator as in this definition?

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$ ...
user avatar
3 votes

an axiomatic framework for clustering by jon kleinberg may have a problem?

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 ...
user avatar
3 votes

Max-sum graph-partition for maximizing intra-edge weights?

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-...
user avatar
3 votes
Accepted

Is there any Bi-criteria PTAS for Metric $k$-Median?

We improve Chandra's bound, as he conjectured was possible, giving an approximation algorithm that opens $f(k,\epsilon)=O(k\log (1/\epsilon))$ facilities to obtain assignment cost at most $1+\epsilon$ ...
user avatar
  • 8,143
2 votes

Good Survey paper for k-means/k-median/k-center/facility-location

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 ...
user avatar
2 votes
Accepted

Divide and Conquer Algorithm for 1-Median Problem

Let $opt^{*}(P_{1})$, $opt^{*}(P_{2})$, and $opt^{*}(P)$ denote the optimal $1$-median costs of $P_{1}$, $P_{2}$, and $P$, repsectively. We show that $\hat{opt} \leq 3 \cdot opt^{*}(P)$ using the ...
user avatar
1 vote

partitioning points in the plane into two clusters to minimize maximum cluster diameter

Theorem 1. There is an $O(n\log n)$-time algorithm for the problem in the post. Proof. We first state two utility lemmas, for an arbitrary edge-weighted graph $G$. We postpone their proofs, which are ...
user avatar
  • 8,143
1 vote

How to build the tree with the "most different" solutions of a clustering?

Have you taken a look at hierarchical clustering algorithms? You can choose among several distance metrics and use a dendrogram to visualize the various splits. Standard packages like scikit-learn &...
user avatar
1 vote

Is there any Bi-criteria PTAS for Metric $k$-Median?

Historically Lin and Vitter showed that one can obtain a $(2+\epsilon, k(1+1/\epsilon))$ bi-criteria approximation via a simple filtering trick with respect to the LP. This was before a constant ...
user avatar
1 vote

kmeans++ for arbitrary metric spaces and general potential function

Though unrelated, this lecture note contains a potential function based neat proof of the $O(\log k)$-approximation.
user avatar
1 vote

The non-metric k-median problem

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

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