AI Paper Atlas

Research map / Learning theory and algorithms / Optimal transport

Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges

Usman Khan, Joseph W Durham

ICML 2026 · Learning theory and algorithms › Optimal transport · approach: Sinkhorn and entropic OT algorithms · 0 citations (OpenAlex)

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 changedWhereMeasuredEffect
prune graph using Sinkhorn shadow transport and solve reduced LP (P2+P3) instead of full P1 LPMAPF-MMOT · grid K=2,500 to 22,500, T=30speedup / cost gap: 3.6x to 7.1x speedup; gap below 10%Improved
increase grid size with shadow pruningP2+P3 pipeline · grid scaling, T=30solve time scaling: K^1.68 -> K^1.15Improved
increase entropic parameter epsilon (ablation)P2+P3 pipeline · K=10,000 grid, lambda=0cost gap vs P1 optimal (%): 2.3 (eps 0.1) -> 17.3 (eps 1.0)Hurt
increase epsilon (ablation)Sinkhorn iterations · K=10,000 gridsweeps to convergence: 307 -> 39Improved
increase shadow-bias lambda in P3 cost (ablation)P2+P3 pipeline · K=10,000 gridcost gap vs P1 optimal (%): 4.3 -> 7.3 (eps 0.2, lambda 0 -> 5.0)Hurt
use extreme epsilon (0.1 or 5.0) with fixed pruning threshold (ablation)P2+P3 pipeline · K=10,000 grid, 260 runsfeasibility: 27 of 260 runs infeasibleHurt
use robust default epsilon=0.2, lambda=0 (ablation)P2+P3 pipeline · K=10,000 gridcost gap / speedup: 4.3% gap at 5x speedupImproved
apply integral projection P3 to fractional shadow P2Sinkhorn-MAPF · 40x40 grid, N=80, T=10transport cost: P2 3160 -> P3 436 (P1 402)Improved
add shadow-based edge pruningP1 LP · grid, large scaleedges eliminated / variables: P3 uses 32-43% of P1 variablesImproved

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy