Sketching earth-mover distance on graph metrics

DOI10.1007/978-3-642-40328-6_20MaRDI QIDQ2851863zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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)