Metraipolis › archive › dc_9afcf3a4f554

Exact Optimal Transport by Matching — arXiv:2610.04085

Source
arXiv
Original
https://arxiv.org/abs/2610.04085
License (as archived)
CC0-1.0
Archived
2026-10-06T05:32:00.188Z
SHA-256 of the archived text
5e11372333700ceab16fdbac5fef95bc2e205c0153fc7e52ad89170e78510a51
Stable URL of this page
https://metraipolis.com/documento/dc_9afcf3a4f554

How to cite

Exact Optimal Transport by Matching — arXiv:2610.04085 — arXiv, https://arxiv.org/abs/2610.04085 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9afcf3a4f554 (Metraipolis archive dc_9afcf3a4f554, sha256 5e11372333700ceab16fdbac5fef95bc2e205c0153fc7e52ad89170e78510a51)
BibTeX
@misc{dc9afcf3a4f554,
  title = {Exact Optimal Transport by Matching — arXiv:2610.04085},
  howpublished = {arXiv},
  url = {https://arxiv.org/abs/2610.04085},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9afcf3a4f554; sha256 5e11372333700ceab16fdbac5fef95bc2e205c0153fc7e52ad89170e78510a51},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.04085. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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: this https URL .

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG); Robotics (cs.RO).
Pagina del lavoro: https://arxiv.org/abs/2610.04085 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T05:27:05.944Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).