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,595
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 ...
- 18.1k
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,595
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,595
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 ...
- 50.9k
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-...
- 6,979
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 ...
- 1,531
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 ...
- 9,595
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,531
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 ...
- 6,979
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,595
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 &...
- 525
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.
- 265
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 ...
- 1,531
Only top scored, non community-wiki answers of a minimum length are eligible