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
4 votes
Accepted

Citation for isometric embeddability of $\ell_2$ into $\ell_p^\binom{n}{2}$ for $p \geq 1$?

This paper by Keith Ball seems to be what you are looking for: Ball, Keith. "Isometric embedding in $\ell_p$-spaces." European Journal of Combinatorics 11.4 (1990): 305-311. Link to the paper ...
Cyrus Rashtchian's user avatar
3 votes
Accepted

A metric space on Turing machines

The map $f$ is not a contraction. To see why, let's take for concreteness $R = 100$. Suppose $w$ is a word and $A,B$ are two machines such that $t_A(w) = 200$ and $t_B(w) = 400$. Then $d(A,B) = 100$...
Nate Eldredge's user avatar
3 votes
Accepted

Finding the size $k$ subset in a metric space that maximizes the min distance between elements

From a quick Google search, it looks like your problem is sometimes called (metric) "facility dispersion." This paper by Ravi, Rosenkrantz, and Tayi seems to prove that your heuristic is a $2$-...
Jason Gaitonde's user avatar
2 votes

Subclasses or characterizations of modular or pseudo-modular planar graphs

The median graphs are a subclass of modular graphs with almost the same definition but where the vertex w is always unique. The squaregraphs (plane graphs in which all bounded faces are quadrilaterals ...
David Eppstein'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

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