I have a N-point metric space defined by the pairwise distance matrix. I want to encode these N points with binary strings, i.e. each point will be mapped to a vertex in a hypercube. The lengths of the edges on the hypercube could be different for different dimensions. The hypercube basically is a hyper-rectangle. Now the questions are the following: 1. Given the dimension of the hyper-rectangle, what is the lower bound of the distortion to the original metric space? 2. How to achieve that, i.e., the lengths of the edges, the vertices for each point? 3. Is the optimal embedding P or NP?

$A = (P,C), |P| = N, C\in [0,1]^{N\times N}$, find a mapping $f:P \rightarrow \mathcal{X} = \prod_{j=1}^D times_{j=1}^D $ { $0,l_j $ }, $l_j > 0$.

such that for any $i,j, \frac{1}{\epsilon} \frac{1}{\mu} C_{ij} \le |f(P_i)-f(P_j)| 1 \le \epsilon C{ij}$, mu C_{ij} $,

where $\epsilon \mu \sim \Omega(g(D,N))$, $g$ is a polynomial function. Thanks a lot!

I have a N-point metric space defined by the pairwise distance matrix. I want to encode these N points with binary strings, i.e. each point will be mapped to a vertex in a hypercube. The lengths of the edges on the hypercube could be different for different dimensions. The hypercube basically is a hyper-rectangle. Now the questions are the following: 1. Given the dimension of the hyper-rectangle, what is the lower bound of the distortion to the original metric space? 2. How to achieve that, i.e., the lengths of the edges, the vertices for each point? 3. Is the optimal embedding P or NP?

$A = (P,C), |P| = N, C\in [0,1]^{N\times N}$, find a mapping $f:P \rightarrow \mathcal{X} = {0,1}^D$ \prod_{j=1}^D 0,l_j $, such that for any $i,j$, $\frac{1}{\epsilon} i,j, \frac{1}{\epsilon} C_{ij} \le |f(P_i)-f(P_j)|1 \le \epsilon C_{ij}$, C{ij}$, where $\epsilon \sim O(g(D,N))$, \Omega(g(D,N))$, $g$ is a polynomial function. Thanks a lot!

I have a N-point metric space defined by the pairwise distance matrix. I want to encode these N points with binary strings, i.e. each point will be mapped to a vertex in a hypercube. The lengths of the edges on the hypercube could be different for different dimensions. The hypercube basically is a hyper-rectangle. Now the questions are the following: 1. Given the dimension of the hyper-rectangle, what is the lower bound of the distortion to the original metric space? 2. How to achieve that, i.e., the lengths of the edges, the vertices for each point? 3. Is the optimal embedding P or NP?

$A = (P,C), |P| = N, C\in [0,1]^{N\times N}$, find a mapping $f:P \rightarrow \mathcal{X} = {0,1}^D$ such that for any $i,j$, $\frac{1}{\epsilon} C_{ij} \le |f(P_i)-f(P_j)| \le \epsilon C_{ij}$, where $\epsilon \sim O(g(D,N))$, $g$ is a polynomial function. Thanks a lot!