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