Dimension Thresholds for Relative-Error Representations of Finite Metrics in Pseudo-Euclidean Spaces
A finite metric space with $N$ points admits an exact representation in a pseudo-Euclidean space of dimension at most $N-1$. We study the minimum dimension required for relative-error approximation of squared distances. Our main result gives an upper bound for arbitrary metrics in terms of local distance ratios: for $4...