Research map / Learning theory and algorithms / Optimal transport
Computing Kantorovich-Wasserstein Distances on $d$-dimensional histograms using $(d+1)$-partite graphs
Gennaro Auricchio, Federico Bassetti, Stefano Gualandi, Marco Veneroni
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the 3-partite graph instead of the bipartite graph | Exact optimal transport with squared ℓ2 cost · DOTmark 32×32, Classic | runtime (seconds): 0.54 (0.05) -> 0.07 (0.01) | Improved |
| Use the 3-partite graph instead of the bipartite graph | Exact optimal transport with squared ℓ2 cost · DOTmark 128×128, Classic | runtime (seconds): 1\,368 (545) -> 36.2 (5.4) | Improved |
| Use the (d+1)-partite graph instead of the bipartite graph | Exact optimal transport with separable cost · Flow Cytometry AML, N=16, d=3 | runtime (seconds): 38.2 (14.0) -> 0.12 (0.02) | Improved |
| Use the (d+1)-partite graph instead of the bipartite graph | Exact optimal transport with separable cost · Flow Cytometry AML, N=16, d=4 | runtime: out-of-memory -> 4.8 (0.84) | Improved |
| Use the (d+1)-partite graph instead of the bipartite graph | Exact optimal transport with separable cost · Flow Cytometry AML, N=32, d=3 | runtime: out-of-memory -> 5.23 (0.69) | Improved |
| Use the 3-partite exact method instead of Improved Sinkhorn λ=1.5 | Optimal transport on regular 2D histograms · DOTmark 32×32, Classic | optimality gap: 9.1% -> 0 | Improved |
| Use Improved Sinkhorn λ=1.5 instead of the exact method | Sinkhorn optimal transport · DOTmark 32×32, GRFrough | optimality gap: 0 -> 31.0% | Hurt |
| Use Improved Sinkhorn λ=1.5 instead of the exact method | Sinkhorn optimal transport · DOTmark 32×32, WhiteNoise | optimality gap: 0 -> 39.2% | Hurt |
Closest papers by meaning
- Tree-Sliced Wasserstein Distance: A Geometric Perspective (ICML 2025 · similarity 0.86)
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.86)
- Distance-Based Tree-Sliced Wasserstein Distance (ICLR 2025 · similarity 0.86)
- Scalable Approximation Algorithms for $p$-Wasserstein Distance and Its Variants (ICML 2025 · similarity 0.85)
- Tree-Sliced Wasserstein Distance with Nonlinear Projection (ICML 2025 · similarity 0.85)
- A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
