Skip to main content
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 ...
Neal Young's user avatar
  • 10.8k
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 ...
Sasho Nikolov's 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 ...
Neal Young's user avatar
  • 10.8k
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 ...
David Eppstein's user avatar
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$ ...
Neal Young's user avatar
  • 10.8k
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 ...
Inuyasha Yagami's user avatar
2 votes
Accepted

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

There is no poly-time approximation algorithm for this problem unless P=NP. For the metric case (when the graph is complete and the edge weights satisfy the triangle inequality), there is a poly-time ...
Neal Young's user avatar
  • 10.8k
2 votes
Accepted

$k-$median problem and filtering technique Lin and Vitter

Consider any fixed location $j$. For any given center $i$, let $X_{ij}$ be the fraction of demand from location $j$ assigned to $i$. Let $d_{ij}$ be the distance from location $j$ to $i$. The LP has ...
Neal Young's user avatar
  • 10.8k
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 ...
Inuyasha Yagami's user avatar
1 vote

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

I think I can show that the problem is NP-hard, even in the case where the graph is unweighted. Specifically, given an undirected graph $G$, and values $p$ and $k$, I want to know if I can partition ...
a3nm's user avatar
  • 9,677
1 vote
Accepted

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 ...
Neal Young's user avatar
  • 10.8k
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 &...
rahulmehta95's 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 ...
Chandra Chekuri's 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.
Sudipta Roy's 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 ...
Inuyasha Yagami's user avatar

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