Additive Approximation Schemes for Low-Dimensional Embeddings
Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins · 2025
Read Additive Approximation Schemes for Low-Dimensional Embeddings by Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-09652.txt.
Introduction
Prashanti Anderson and 2 co-authors give the first efficient additive approximation scheme for a classic embedding problem in a 2025 algorithms paper. The task fits points in a low-dimensional Euclidean space so pairwise distances match given data as closely as possible, a practice known for decades as multidimensional scaling. Even the one-dimensional case is provably hard, and nothing efficient was known for higher dimensions.
Their scheme runs in polynomial time and lands within a small additive error of the optimum for the k-dimensional metric violation problem. Earlier work had managed only a logarithmic factor in one dimension, and a long-open question asked whether such a scheme existed at all. The result moves a seventy-year-old statistical workhorse onto firmer algorithmic ground.
Catalog record
| CREATOR | Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 172 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-09652