# Tag Info

6

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 understanding correctly, thanks. Consider a cluster $X$ consisting of a rooted star: a root $r$ and $n-1$ nodes $v_1,v_2,\ldots, v_{n-1}$ such that $d(r, v_i) = 1$...

5

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.

4

Think of the hypercube as a graph $G$. Allowing arbitrary edge lengths implies that you can use edge lengths $0$ and $\infty$ to get a minor of $G$ on which you can put edge lengths. The hypercube has sufficiently large expansion that it contains, as a minor, a clique of size about $\sqrt{N}$ (ignoring polylog factors) where $N$ is the number of nodes of the ...

4

In general there are all kinds of lower bounds for embedding an arbitrary metric on the hypercube into $\ell_1$. For example, the edit distance cannot be embedded with better than $\log n$ distortion. Note that the Hamming distance itself embeds isometrically in $\ell_1$, so you can't expect to prove any nontrivial lower bound over all metrics on the ...

4

Hausdorff distance is what you are looking for.

4

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 here: https://www.sciencedirect.com/science/article/pii/S019566981380131X

3

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$. Now $t_{f(A)}(w) = 100 + |w| + 2$ and $t_{f(B)}(w) = 200 + |w| + 2$, so $|t_{f(A)}(w) - t_{f(B)}(w)| = 100$ and $d(f(A),f(B)) = 100$ also. But to have a ...

3

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 a matrix, and then define the code to be the span of the columns of the matrix. The $\epsilon$-biased property of the set is equivalent to saying that the ...

3

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$-approximation, and that this factor is actually optimal by a reduction to clique. I skimmed it, so I might be missing some subtle points, but the idea of the proof ...

2

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 and all vertices either have degree 4 or belong to the unbounded face) form a natural and interesting subclass of the planar median graphs. I believe that all ...

1

Though unrelated, this lecture note contains a potential function based neat proof of the $O(\log k)$-approximation.

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