Exact Optimal Transport by Matching

Dmitry Kamenetsky

cs.DSOct 2, 2026

Exact Optimal Transport by Matching

Authors: Dmitry Kamenetsky

Abstract

Balanced discrete optimal transport between n sources and n targets of unit mass is exactly the minimum-cost assignment problem-a bipartite perfect matching-and is therefore solvable exactly by industrial matching engines in milliseconds to seconds. We ask when the exact approach beats the standard approximate alternatives, entropic Sinkhorn and its accelerated variant Greenkhorn, and make the sparse-exact side certified by a textbook LP dual-feasibility clip. Three contributions. (i) Measurement: on dense 2-D instances, exact matching (Jonker-Volgenant) is faster and strictly more accurate than either approximate method throughout the moderate-n regime (0.01 s at n=500 to 11.5 s at n=8000); reaching a 1% quality target on the same hardware requires roughly 10-80 min for Greenkhorn (factors 4e2-6e4 over exact; plain Sinkhorn is 20-650x slower still), a rough power-law projection beyond the measured range. Greenkhorn's measured speedup over plain Sinkhorn is only 1.0-1.5x on most converged cells. (ii) A simple kNN-pool gap certificate: given a pool matching and its Blossom dual, a one-pass O(n^2) clip produces a dense-feasible lower bound; combined with the Sinkhorn dual potential (valid at every iterate, not just at convergence), the bound is valid on all 45 measured configurations and tightens monotonically with k. (iii) A multi-robot task-allocation sanity check where the discrete plan is the deliverable: per-round exact assignment costs 0.1-68 ms, while a Sinkhorn-plus-hardening pipeline costs 0.12-15.9 s and accumulates 6-27% extra travel over 15 rounds. The Sinkhorn family's large-n dense regime is acknowledged and left untouched. Code, data, and results under MIT: https://github.com/dimkadimon/OT-Blossom.

Figures & tables

$n$	exact cost	$t(\mathrm{exact})$
500	2064.1	0.01 s
1000	3107.0	0.06 s
2000	4146.4	0.23 s
4000	6963.2	2.16 s
8000	10873.4	11.48 s

Table 1: Dense exact assignment (Jonker–Volgenant), uniform seed 7. Costs use the total-mass convention; divide by

n

for the per-unit-mass value common in the OT literature. Times are single runs.

$n$	$f$	gap %	$t(\mathrm{Sinkhorn})$
500	0.05	+58.41	10 s
500	0.02	+15.02	34 s
500	0.01	+5.42	74 s
500	0.005	+2.09	400 s (capped)
1000	0.05	+91.40	32 s
1000	0.02	+24.19	111 s

Table 2: Vanilla Sinkhorn (log domain, marginal tolerance

10^{-9}

), uniform seed 7. Gaps are relative to the exact optimum computed on the rounded milliunit costs.

$n$	$t(\mathrm{exact})$	$t(\mathrm{Sinkhorn\ at\ }f^{*})$	$t(\mathrm{Greenkhorn\ at\ }f^{*})$
500	0.01 s	$\sim\!200$ min	$\sim\!10$ min
1000	0.06 s	$\sim\!700$ min	$\sim\!12$ min
2000	0.23 s	$\sim\!3000$ min	$\sim\!20$ min
4000	2.16 s	$\sim\!10^{4}$ min	$\sim\!40$ min
8000	11.48 s	$\sim\!5{\times}10^{4}$ min	$\sim\!80$ min

Table 3: Wall time to reach

1\%

gap for Greenkhorn, extrapolated as described in the text (rough order-of-magnitude, deliberately rounded up to one or two significant figures; see caveats). The Sinkhorn column is a coarser order-of-magnitude estimate: per-step work scales as

O(n^{2})

for Sinkhorn vs

O(n)

for Greenkhorn on the kNN support, implying Sinkhorn is

20

–

650\times

slower than Greenkhorn at this

f^{*}

(extrapolated; the actually measured Greenkhorn/vanilla ratios in Table 4 are

0.93

–

5.0\times

on the cells that converged).

$n$	$f$	gap S %	$t(S)$ s	gap G %	$t(G)$ s	steps(G)	$t(S)/t(G)$
500	0.05	+58.41	10	+58.41	10	260k	$0.93\times$
500	0.02	+15.02	34	+15.01	27	760k	$1.26\times$
500	0.01	+5.42	74	+5.40	52	1.48M	$1.45\times$
500	0.005	+2.09	400 †	+2.07	94	2.82M	$4.27\times$
1000	0.05	+91.40	32	+91.40	25	520k	$1.28\times$
1000	0.02	+24.19	111	+24.17	77	1.82M	$1.44\times$

Table 4: Vanilla Sinkhorn (S) vs Greenkhorn (G), uniform seed 7. † 400 s cap (vanilla did not converge there). Times are rounded to integer seconds for display; speed ratios in the final column are computed from the unrounded wall times (so the

n=500,f=0.05

row shows

10

s vs

10

s but the ratio is

0.93\times

). All Greenkhorn runs stopped on a cost plateau before reaching marginal tolerance

10^{-9}

(typical plateau

10^{-6}

–

10^{-3}

); cost agreement

\leq 0.04\%

in every cell, which bounds the cost error from early stopping well below the percent-level gaps we report.

$k$ label	pool edges	cost	gap vs exact	$t(\mathrm{sparse})$
4	19,973	5757.7	+38.861%	0.02 s
8	35,918	4388.6	+5.841%	0.05 s
16	67,685	4170.5	+0.581%	0.08 s
32	130,860	4147.7	+0.032%	0.18 s
64	255,711	4146.5	+0.003%	0.40 s
256	962,049	4146.4	+0.000%	1.76 s

Table 5:

k

NN-pool exact assignment (Blossom VI),

n=2000

uniform seed 7; dense exact

=4146.4

0.23\,

s. Edge counts reflect a

k+1

per-side budget in the original driver (see text); gaps are computed against the unrounded exact optimum.

family (#configs)	$k=16$	$k=32$	$k=64$
uniform (5)	2.57–6.26%	0.07–0.70%	0.01–0.02%
clustered (5)	5.61–38.25%	1.03–21.88%	0.17–5.90%
1-D+noise (5)	11.94–17.35%	1.89–3.59%	0.24–0.79%
all families, true gaps	0.52–3.84%	0.010–2.60%	0.000–1.85%

Table 6: Certificate width by family (range over configurations; 15 cells at each

k

). The bottom row pools true gaps across all families; all 45 cells carry

\mathrm{LB}>0

Figure 1: Exact (Jonker–Volgenant) vs vanilla Sinkhorn and Greenkhorn on the dense uniform grid (seed 7). Left: wall time (log-log); solid lines are measured points at

f=0.01

(smallest regularization that converged on the measured grid), dashed lines continue the empirical log-log slope, and star markers are the rough Table 3 extrapolation to the

1\%

quality target. Right: gap to exact (semi-log) at

f\in\{0.05,0.02,0.01\}

(Sinkhorn; Greenkhorn at

f=0.01

overlaps the Sinkhorn curve to within line width); at

n=2000

the

f=0.01

runs did not converge within the 400 s cap. At

f=0.01

the gap ranges from

5.4\%

n=500

8.6\%

n=1000

, i.e. well above the

1\%

target. Exact is below both approximate curves at every measured

n

in both time and quality. Both panels share the same

n

-axis.

Figure 2: Certificate per configuration. Left: certified width (bars) vs true gap (dots) for

k\in\{16,32,64\}

—the bar is always at or above the dot. Right: certified width vs

k

, monotone decreasing on every configuration.

$n$	seed	travel (myopic exact)	greedy	Sinkhorn+hard	gap greedy	gap Sinkh.
50	7	10232.8	12353.3	10930.4	+20.72%	+6.82%
50	8	10531.8	12357.2	11134.9	+17.33%	+5.73%
200	7	21835.6	28718.1	24955.1	+31.52%	+14.29%
200	8	23804.5	30051.8	26802.5	+26.24%	+12.59%
800	7	47327.7	64986.7	59959.2	+37.31%	+26.69%
800	8	49050.9	66519.9	61229.6	+35.61%	+24.83%

Table 7: Total travel distance over 15 rounds; gaps are relative to the myopic-exact policy (see text for the global-optimality caveat).

Figure 3: Left: episode travel distance vs

n

(the quality tax compounds with

n

). Right: cost of the assignment step per round (log scale): exact matching is

0.1

–

68

ms/round; the Sinkhorn pipeline is

10^{2}

–

10^{3}\times

slower. The greedy serial baseline is faster at large

n

than its

O(n^{2})

worst case suggests because in practice its earlier picks remove the most-attractive edges cheaply; even so greedy remains

3

–

10\times

slower than exact at every measured

n

while producing a much worse plan.

Situation	Recommended solver	Why
Integer plan required (MRTA, dispatch, matching per se)	Dense exact (JV) or sparse pool + certificate	Fractional plans are not physically realizable; hardening a Sinkhorn plan adds $6$ to $37\%$ travel cost in our application and is slower at $n\leq 10^{3}$ .
1-D / near-Monge (sorted-order structure)	Quantile (sort) map, Proposition 2	$O(n\log n)$ time, no matrix; scales to $n=10^{6}$ in $0.1$ s.
Local / $k$ NN structure (e.g. Euclidean geometry, moderate dim.)	$k$ NN-pool exact (Blossom VI) + dual-repair certificate	At $k=32$ the certificate is tight ( $\leq 0.7\%$ ) on uniform instances; pool solve is sub-second.
Dense, no structure, fractional plan acceptable, $n\lesssim 10^{4}$	Dense exact (JV)	Exact is milliseconds to seconds at this scale; Sinkhorn pays a regularization tax and is $100$ – $1000\times$ slower.
Dense, fractional plan acceptable, $n\gg 10^{4}$ (past memory wall)	Well-tuned Sinkhorn/Greenkhorn (POT, GPU)	Dense matrix no longer fits; Sinkhorn runs in near-linear memory. We do not benchmark this regime.

Table 8: Empirical decision rule derived from the measurements in Sections 6 – 7 .

Optimal Transport

Optimal transport compares and transforms probability distributions by finding low-cost ways to move mass between them.

See all 287 papers

Aug 28, 2026

SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport

Entropic optimal transport (EOT) has been shown to offer a computationally tractable approximation to exact optimal transport. However, the standard Sinkhorn-Knopp algorithm has two main limitations. First, given discrete measures with

N

points, each iteration requires

O(N^2)

operations, which restricts its use on large-scale datasets (e.g.

N\geq10^4

). Second, it uses the independent coupling as a reference measure for regularisation. This assigns mass to high-cost transport edges at moderate regularisation strengths. We propose SinkSLOT, which addresses both limitations by putting forth the expected sliced lifted transport plan as a natural way to sparsify the Gibbs kernel with a non-independent prior coupling. We prove that: 1) SinkSLOT converges; 2) with

L

slices, each resulting sparse Sinkhorn iteration costs

O(LN)

; and 3) the resulting objective is a divergence requiring no debiasing. Experiments on synthetic benchmarks show that SinkSLOT delivers substantial speedups over state-of-the-art dense and sparse EOT methods. We also demonstrate the applicability of the proposed divergence in a gradient flow experiment. The code is publicly available at https://github.com/cai4cai/SinkSLOT.

Ian Hsieh, Soumya Snigdha Kundu, Tom Vercauteren +1

Sorbonne Université, Institut du Cerveau - Paris Brain Institute - ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, 75013 Paris, France · King’s College London, UK

Optimal Transport Entropy Regularization

Ask PDF

Aug 6, 2026

Potential Matching Optimal Transport: Continuous Normalizing Flows for Exact $p$ -Wasserstein Dynamics

We introduce Potential Matching Optimal Transport (PMOT), a potential-flow framework for general

p

-cost optimal transport with

c_p(x,y)=\|x-y\|^p

. PMOT parameterizes the CNF velocity field with a scalar potential in the generalized Benamou--Brenier form for the chosen exponent

p

. It trains the potential gradient with a self-induced matching loss along straight bridges determined by the model's own endpoints, while allowing flexible terminal distribution matching. Our main result establishes zero-loss exactness: under the stated regularity, exact terminal matching, and uniqueness assumptions, any zero-loss solution satisfies the generalized Benamou--Brenier optimality system and recovers the corresponding

p

-optimal transport map and dynamics. On synthetic benchmarks, PMOT learns

p

-specific maps that agree with the corresponding

p

-matched OT references. It also remains competitive as a likelihood-based density model on high-dimensional tabular data, and an MMD-based color transformation experiment demonstrates flexible sample-based terminal matching.

Lishuo Zhang, Ruizhi Huang, Yang Yu +1

School of Mathematical Sciences, Shanghai Jiao Tong University · Institute of Natural Sciences, MOE-LSC, Shanghai Jiao Tong University

Flow Matching Continuous Normalizing Flows Optimal Transport

Ask PDF

Sep 27, 2026

Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory

We characterize Bregman Douglas-Rachford splitting (BDRS) for unregularized discrete optimal transport and develop an anytime primal-dual certificate in linear memory. We first establish that BDRS coincides with warm-started Inexact Proximal point method for exact Optimal Transport (IPOT) using a single inner Sinkhorn iteration. By eliminating the primal transport plan from the updates, we derive an equivalent dual formulation that reveals BDRS as annealed Sinkhorn under an implicit inverse-linear temperature schedule, with an additional log-scaling momentum term and a cooler kernel. While this explains the role of the temperature parameter in BDRS as an initial temperature, it also reduces the solver's memory requirement from quadratic to linear. Utilizing this annealing perspective, we introduce overrelaxed BDRS, which combines annealing and overrelaxed scaling within a single recursion. We derive a primal-dual certificate for both methods that can be evaluated in linear memory without transport plan construction, thus providing a computable stopping rule. On the DOTmark benchmark, combining momentum with the cooler kernel produces substantially smaller optimality gaps than annealed Sinkhorn under the same schedule. For pixel-level color transfer between

1024\times1024

images, BDRS attains a lower repaired transport cost than MDOT-TNT with a 9

\times

speed up, reaching a relative duality gap of

1.59\%

in 24 minutes. We further demonstrate a color transfer with

4238\times2365

images, yielding 10 million pixels per image and approximately one hundred trillion implicit transport entries, reaching a best relative duality gap of

2.41\%

and

2.80\%

within 35 hours in each direction on a single NVIDIA L40S GPU.

Samuel J. K. Chin, Maximilian Schiffer

MIT · HEC Paris

Primal-Dual Optimization Optimal Transport

Ask PDF

Abstract

Optimal Transport

Explore similar work

SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport

Potential Matching Optimal Transport: Continuous Normalizing Flows for Exact ppp-Wasserstein Dynamics

Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory

Potential Matching Optimal Transport: Continuous Normalizing Flows for Exact $p$ -Wasserstein Dynamics