On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows

DOI10.1137/19M1261195zbMath1450.90008arXiv1804.00445OpenAlexW3084377872MaRDI QIDQ5124004

Stefano Gualandi, Marco Veneroni, Federico Bassetti

Publication date: 17 September 2020

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.00445

zbMATH Keywords

transportation problemWasserstein distanceKantorovich metricnetwork simplexuncapacitated minimum cost flow problem

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (5)

Kantorovich distance on finite metric spaces: Arens-Eells norm and CUT norms ⋮ Approximate Wasserstein attraction flows for dynamic mass transport over networks ⋮ On the structure of optimal transportation plans between discrete measures ⋮ Density estimation of multivariate samples using Wasserstein distance ⋮ Multilevel Optimal Transport: A Fast Approximation of Wasserstein-1 Distances

Uses Software

• EMD
• SIFT
• DOTmark
• Wasserstein GAN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Long history of the Monge-Kantorovich transportation problem
• Signature classes of transportation polytopes
• A production-transportation problem with stochastic demand and concave production costs
• Approximation schemes for NP-hard geometric optimization problems: a survey
• A parallel method for earth mover's distance
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• The earth mover's distance as a metric for image retrieval
• A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• On minimum Kantorovich distance estimators
• On the Hitchcock distribution problem
• Convolutional wasserstein distances
• Minimum-cost flow algorithms: an experimental evaluation
• Scaling algorithms for unbalanced optimal transport problems
• Finding minimum-cost circulations by canceling negative cycles
• On the Number of Markoff Numbers Below a Given Bound
• Nonparametric Validation of Similar Distributions and Assessment of Goodness of Fit
• Inference for Empirical Wasserstein Distances on Finite Spaces
• Earth mover's distances on discrete surfaces
• Primitive lattice points in convex planar domains
• Efficient implementation of the Goldberg–Tarjan minimum-cost flow algorithm
• Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Asymptotic Properties and Robustness of Minimum Dissimilarity Estimators of Location-scale Parameters
• Sur un théorème de M. V. Jarník
• Combinatorial optimization. Theory and algorithms.
• Optimal Transport
• On the history of the transportation and maximum flow problems

This page was built for publication: On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows