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
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 ...
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$...
- 146
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$-...
- 800
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 ...
- 50.9k
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
Only top scored, non community-wiki answers of a minimum length are eligible