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 ...
  • 9,223
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 ...
4 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$ ...
  • 9,223
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 ...
  • 9,223
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 ...
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-...
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 ...
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 ...
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 ...
  • 9,223
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 &...
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 ...
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.
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 ...

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