We show that any $n$‑point Euclidean metric can be embedded into the real line by a non‑expansive map with average distortion bounded by $$O\!\left(\sqrt{\frac{\log n}{\log\log n}}\right)$$, matching the known lower bound. The construction uses a random projection followed by a piecewise‑linear scaling that preserves distances from expanding while tightly controlling the overall distortion. Two notable applications follow. First, the embedding yields a cut‑player strategy for the undirected cut‑matching game that attains the optimal spectral guarantee: the potential function’s spectral decay per round reaches the theoretical limit. Second, the same technique gives an improved spectral approximation for vertex expansion in high‑degree graphs, achieving a factor $O!\left(\sqrt{\frac{\log d}{\log\log d}}\right)$ (where $d$ is the maximum degree), which beats the previous $O(\sqrt{\log d})$ bound.
Review: The paper provides a tight average‑distortion bound for Euclidean‑to‑line embeddings and translates it into optimal or improved spectral algorithms for two classic graph problems, highlighting a deep connection between geometric embeddings and discrete optimization.