hello
Let (A, d) be an n-point metric space
for $t \geq 1$,the task it to find 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*d(x,y)$ where $d_1$ denotes the $l_1$ norm.
Is it possible to check if f exists, given t using linear programing?
andy
The question is slightly ambiguous, since it doesn't specify how large the linear program can be or how much preprocessing can be devoted to producing it. However, if everything is required to run in polynomial time, then the answer is no, assuming ${\rm P} \ne {\rm NP}$. Specifically, take $t=1$, so we are trying to determine whether there is an exact embedding in $\ell_1^m$. If we don't specify the dimension $m$, then this problem is NP-hard (see the book Geometry of Cuts and Metrics by Deza and Laurent). However, if any $m$ works, then we can take $m = \binom{n}{2}$ (this follows from basic facts about the cut cone; again see Deza and Laurent). Since linear programs can be solved in polynomial time, the embedding problem can't be reduced to a linear program.
What makes this a little tricky is that it can halfway be done. Suppose we focus on two points $x$ and $y$ and introduce $2m$ variables $a_1,\dots,a_m$ and $b_1,\dots,b_m$ for the coordinates of $f(x)$ and $f(y)$. It's not hard to express the upper bounds on $d_1(f(x),f(y))$ via linear constraints. For example, we can add in $m$ more variables $c_1,\dots,c_m$ and the inequalities $a_i-b_i \le c_i$ and $b_i-a_i \le c_i$ (so that $|a_i-b_i| \le c_i$). Now the upper bound amounts to $c_1+\dots+c_m \le t d(x,y)$. This looks pretty good: we can do it for each pair of points, and thus encode in our linear program the constraint that the $\ell_1$ distances can't be too large.
However, the other direction just doesn't work. There's a fundamental difference in how well linear programs can deal with absolute values in upper or lower bounds. You can encode $|u| \le v$ by the two constraints $u \le v$ and $-u \le v$, but $u \le |v|$ can't be handled similarly. (Its solution set isn't even convex. It amounts to requiring that $u \le v$ or $u \le -v$, but not both.) That ruins all straightforward attempts to solve this problem by linear programming, and the NP-hardness shows that the difficulty is real.
