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

CREATORPrashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE172 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-09652

Browse the full library · About the Tower of Babel