1
$\begingroup$

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

  • 0
    by ncr(n,2) i mean n choose 22011-04-23
  • 0
    @andy: I typeset "n choose 2" for you. The LaTeX code is \binom{n}{2}.2011-04-23
  • 0
    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$.2011-04-23
  • 1
    Also, what's the cut metric?2011-04-23
  • 0
    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.2011-04-23
  • 0
    @Yuval: No its not, d can be any distance, for example the "edit distance", for which it is known that it has an $\Omega(\log n)$ embedding into l12011-04-23
  • 0
    @andy: This is consistent with your definition, which just states that $t$ exists. It doesn't constrain it as a function of $n$.2011-04-23
  • 0
    hmm, i interpreted the "exists t"-statement as f having distortion t2011-04-24

0 Answers 0