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 ...
user avatar
  • 8,228
5 votes
Accepted

Compute lowest dimensional polytope from a given set of sign vectors

This is equivalent to computing the sign rank of a matrix, which is NP-hard as shown in this paper. So you cannot expect too efficient of an algorithm.
user avatar
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 ...
user avatar
4 votes
Accepted

Are there Similar Distance Binary Error Correcting Codes?

Every $\epsilon$-biased set gives a code whose minimal relative distance is $0.5 - \epsilon$ and maximal relative distance is $0.5 + \epsilon$. To see it, write the elements of the set as the rows of ...
user avatar
  • 5,055
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$...
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$-...
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 ...
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.
user avatar

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