{"ID":2884259,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.06774","arxiv_id":"2508.06774","title":"Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair","abstract":"We give a reduction from $(1+\\varepsilon)$-approximate Earth Mover's Distance (EMD) to $(1+\\varepsilon)$-approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given $p\\in [1, 2]$ and two sets of $n$ points $X,Y \\subseteq (\\mathbb R^d,\\ell_p)$, their EMD is the minimum cost of a perfect matching between $X$ and $Y$, where the cost of matching two vectors is their $\\ell_p$ distance. Further, CP is the basic problem of finding a pair of points realizing $\\min_{x \\in X, y\\in Y} ||x-y||_p$. Our contribution is twofold: we show that if a $(1+\\varepsilon)$-approximate CP can be computed in time $n^{2-φ}$, then a $1+O(\\varepsilon)$ approximation to EMD can be computed in time $n^{2-Ω(φ)}$; plugging in the fastest known algorithm for CP [Alman, Chan, Williams FOCS'16], we obtain a $(1+\\varepsilon)$-approximation algorithm for EMD running in time $n^{2-\\tildeΩ(\\varepsilon^{1/3})}$ for high-dimensional point sets, which improves over the prior fastest running time of $n^{2-Ω(\\varepsilon^2)}$ [Andoni, Zhang FOCS'23]. Our main technical contribution is a sublinear implementation of the Multiplicative Weights Update framework for EMD. Specifically, we demonstrate that the updates can be executed without ever explicitly computing or storing the weights; instead, we exploit the underlying geometric structure to perform the updates implicitly.","short_abstract":"We give a reduction from $(1+\\varepsilon)$-approximate Earth Mover's Distance (EMD) to $(1+\\varepsilon)$-approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given $p\\in [1, 2]$ and two sets of $n$ points $X,Y \\subseteq (\\mathbb R^d,\\ell_p...","url_abs":"https://arxiv.org/abs/2508.06774","url_pdf":"https://arxiv.org/pdf/2508.06774v1","authors":"[\"Lorenzo Beretta\",\"Vincent Cohen-Addad\",\"Rajesh Jayaram\",\"Erik Waingarten\"]","published":"2025-08-09T02:00:53Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\"]","methods":"[]","has_code":false}