More Like this

1. Transport inequalities on Euclidean spaces for non-Euclidean metrics

   https://doi.org/10.1007/s00041-020-09766-2  

   Bobkov, S. G.; Ledoux, M. (January 2020, Journal of fourier analysis applications)

   null (Ed.)

   We explore upper bounds on Kantorovich transport distances between probability measures on the Euclidean spaces in terms of their Fourier-Stieltjes transforms, with focus on non-Euclidean metrics. The results are illustrated on empirical measures in the optimal matching problem on the real line. 

   more » « less
2. Online Euclidean Spanners

   https://doi.org/10.4230/LIPIcs.ESA.2021.16  

   Bhore, Sujoy; Tóth, Csaba D. (August 2021, 29th Annual European Symposium on Algorithms)

   Mutzel, Petra; Pagh, Rasmus; Herman, Grzegorz (Ed.)
3. Non-Euclidean navigation

   https://doi.org/10.1242/jeb.187971  

   Warren, William H. (February 2019, The Journal of Experimental Biology)
4. Separating subadditive Euclidean functionals

   Frieze, A; Pegden, W (January 2017, Random structures & algorithms)

   The classical Beardwood-Halton-Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form $$\beta \sqrt n$$ for the minimum length of a Traveling Salesperson Tour throuh $$n$$ random points in the unit square, and in the decades since it was proved, the existence of such formulas has been shown for other such \emph{Euclidean functionals} on random points in the unit square as well. Despite more than 50 years of attention, however, it remained unknown whether the minimum length TSP through $$n$$ random points in $[0,1]^2$ was asymptotically distinct from its natural lower bounds, such as the minimum length spanning tree, the minimum length 2-factor, or, as raised by Goemans and Bertsimas, from its linear programming relaxation. We prove that the TSP on random points in Euclidean space is indeed asymptotically distinct from these and other natural lower bounds, and show that this separation implies that branch-and-bound algorithms based on these natural lower bounds must take nearly exponential ($$e^{\tilde \Omega(n)}$$) time to solve the TSP to optimality, even in average case. This is the first average-case superpolynomial lower bound for these branch-and-bound algorithms (a lower bound as strong as $$e^{\tilde \Omega (n)}$$ was not even been known in worst-case analysis). 

   more » « less
5. Optimal (Euclidean) Metric Compression

   https://doi.org/10.1137/20M1371324  

   Indyk, P.; Wagner, T. (January 2022, SIAM journal on computing)

   We study the problem of representing all distances between n points in Rd, with arbitrarily small distortion, using as few bits as possible. We give asymptotically tight bounds for this problem, for Euclidean metrics, for ℓ1 (a.k.a.~Manhattan) metrics, and for general metrics. Our bounds for Euclidean metrics mark the first improvement over compression schemes based on discretizing the classical dimensionality reduction theorem of Johnson and Lindenstrauss (Contemp.~Math.~1984). Since it is known that no better dimension reduction is possible, our results establish that Euclidean metric compression is possible beyond dimension reduction. 

   more » « less