2026-09-22T03:54:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27259 2026-09-05T20:16:38Z ddc:004 open_access

Fast Algorithms for Continuous Optimal Transport Between Histograms Agarwal, Pankaj K. Raghvendra, Sharath Yao, Keegan Optimal transport min-cost flow minimum-weight matching quadtrees approximation algorithms dynamic optimal transport algorithm We give the first (relative) (1+ε)-approximation algorithm for the continuous optimal transport (OT) problem between two axis-aligned histograms in the plane, each of which is represented as a piecewise-constant function over a rectangular subdivision. Our algorithm runs in nearly quadratic time in the complexity of the histograms in the worst case. In contrast to the discrete and semi-discrete optimal transport problems, which always admit linear-size OT plans, we demonstrate that there is a quadratic lower bound on the complexity of even a (1+ε)-approximate OT plan in the continuous setting in the worst case. This suggests that the runtime of our approximation algorithm nearly matches the worst-case lower-bound complexity of an explicit (1+ε)-approximate OT plan between two histograms. We additionally provide near-linear time algorithms with either weaker approximation guarantees or restrictions on the input histograms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Sharath Raghvendra and Keegan Yao 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.123 urn:nbn:de:0030-drops-272595 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.123 eng https://creativecommons.org/licenses/by/4.0/legalcode