# $l_1$-metric and cut metric equivalence

I would like to show that the following two statements are equivalent.

Let $(A,d)$ be an $n$-point metric space and $B$ a set of $\binom{n}{2}$ pairs of points of $A$.

Then $\exists t \geq 1$, an integer $m$, and an embedding $f : A \rightarrow R^m$ s.t. $\forall x,y \in A$ : $d(x,y) \leq d_1(f(x), f(y)) \leq t\cdot d(x,y)$ where $d_1$ denotes the $l_1$ norm.

And the statement:

For every $a,b : B \rightarrow R^+$ such that $$\sum_{(x,y) \in B} a(x,y)d(x,y) \leq \sum_{(x,y) \in B} b(x,y)d(x,y),$$ there exists a set $S \subseteq A$ (not empty, not equal to $A$), such that $$\sum_{(x,y) \in B} a(x,y)d_S(x,y) \leq \sum_{(x,y) \in B} b(x,y)d_S(x,y)$$ where $d_S$ is the cut metric of the set S.

I understand that minimizing the $l_1$ metric is the same as minimizing the cut metric. Thus my idea was to formulate the first statement as a Linear Program but I didn't get any useful insights out of it.

Does anyone have an idea?

Thanks andy

• by ncr(n,2) i mean n choose 2 – andy Apr 23 '11 at 2:55
• @andy: I typeset "n choose 2" for you. The LaTeX code is \binom{n}{2}. – Mike Spivey Apr 23 '11 at 3:18
• Isn't the first statement always true (assuming $d(x,y) = 0$ implies $x = y$, otherwise it's plainly false)? Choose the images $f(A)$ to be far apart (farther than the largest $d(x,y)$), and choose $t$ to be large enough. This works even for $m = 1$. – Yuval Filmus Apr 23 '11 at 3:40
• Also, what's the cut metric? – Yuval Filmus Apr 23 '11 at 3:40
• Given a Graph G=(V,E) a cut metric §d_S§ for a subset S of the nodes assign a distance of one to all node pairs for which the edge crosses S and $\bar{S}$ and 0 else. – andy Apr 23 '11 at 17:05