Sketching earth-mover distance on graph metrics

DOI10.1007/978-3-642-40328-6_20zbMATH Open1405.68250OpenAlexW1035080392MaRDI QIDQ2851863FDOQ2851863

Authors: Andrew McGregor, Daniel M. Stubbs 

Publication date: 4 October 2013

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-40328-6_20

Recommendations

• Space-Efficient Approximation Scheme for Circular Earth Mover Distance
• Sublinear time algorithms for earth mover's distance
• Computing the Monge-Kantorovich distance
• Near-optimal (Euclidean) metric compression
• Sketching and embedding are equivalent for norms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distance in graphs (05C12)

Cited In (7)

• Wasserstein distance and metric trees
• Projection-based techniques for high-dimensional optimal transport problems
• On the estimation of latent distances using graph distances
• On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions
• Sublinear time algorithms for earth mover's distance
• Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance
• The ultrametric Gromov-Wasserstein distance

This page was built for publication: Sketching earth-mover distance on graph metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851863)