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

  • $\begingroup$ by ncr(n,2) i mean n choose 2 $\endgroup$ – andy Apr 23 '11 at 2:55
  • $\begingroup$ @andy: I typeset "n choose 2" for you. The LaTeX code is \binom{n}{2}. $\endgroup$ – Mike Spivey Apr 23 '11 at 3:18
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Apr 23 '11 at 3:40
  • 1
    $\begingroup$ Also, what's the cut metric? $\endgroup$ – Yuval Filmus Apr 23 '11 at 3:40
  • $\begingroup$ 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. $\endgroup$ – andy Apr 23 '11 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.