DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.123

Fast Algorithms for Continuous Optimal Transport Between Histograms

Authors: Pankaj K. Agarwal, Sharath Raghvendra, and Keegan Yao

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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.

Cite as

Pankaj K. Agarwal, Sharath Raghvendra, and Keegan Yao. Fast Algorithms for Continuous Optimal Transport Between Histograms. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 123:1-123:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ESA.2026.123,
  author =	{Agarwal, Pankaj K. and Raghvendra, Sharath and Yao, Keegan},
  title =	{{Fast Algorithms for Continuous Optimal Transport Between Histograms}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{123:1--123:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.123},
  URN =		{urn:nbn:de:0030-drops-272595},
  doi =		{10.4230/LIPIcs.ESA.2026.123},
  annote =	{Keywords: Optimal transport, min-cost flow, minimum-weight matching, quadtrees, approximation algorithms, dynamic optimal transport algorithm}
}

Document

DOI: 10.4230/LIPIcs.CPM.2021.25

Optimal Completion and Comparison of Incomplete Phylogenetic Trees Under Robinson-Foulds Distance

Authors: Keegan Yao and Mukul S. Bansal

Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)

Abstract

The comparison of phylogenetic trees is a fundamental task in phylogenetics and evolutionary biology. In many cases, these comparisons involve trees inferred on the same set of leaves, and many distance measures exist to facilitate such comparisons. However, several applications in phylogenetics require the comparison of trees that have non-identical leaf sets. The traditional approach for handling such comparisons is to first restrict the two trees being compared to just their common leaf set. An alternative, conceptually superior approach that has shown promise is to first complete the trees by adding missing leaves so that the completed trees have identical leaf sets. This alternative approach requires the computation of optimal completions of the two trees that minimize the distance between them. However, no polynomial-time algorithms currently exist for this optimal completion problem under any standard phylogenetic distance measure. In this work, we provide the first polynomial-time algorithms for the above problem under the widely used Robinson-Foulds (RF) distance measure. This hitherto unsolved problem is referred to as the RF(+) problem. We (i) show that a recently proposed linear-time algorithm for a restricted version of the RF(+) problem is a 2-approximation for the RF(+) problem, and (ii) provide an exact O(nk²)-time algorithm for the RF(+) problem, where n is the total number of distinct leaf labels in the two trees being compared and k, bounded above by n, depends on the topologies and leaf set overlap of the two trees. Our results hold for both rooted and unrooted binary trees. We implemented our exact algorithm and applied it to several biological datasets. Our results show that completion-based RF distance can lead to very different inferences regarding phylogenetic similarity compared to traditional RF distance. An open-source implementation of our algorithms is freely available from https://compbio.engr.uconn.edu/software/RF_plus.

Cite as

Keegan Yao and Mukul S. Bansal. Optimal Completion and Comparison of Incomplete Phylogenetic Trees Under Robinson-Foulds Distance. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{yao_et_al:LIPIcs.CPM.2021.25,
  author =	{Yao, Keegan and Bansal, Mukul S.},
  title =	{{Optimal Completion and Comparison of Incomplete Phylogenetic Trees Under Robinson-Foulds Distance}},
  booktitle =	{32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
  pages =	{25:1--25:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-186-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{191},
  editor =	{Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.25},
  URN =		{urn:nbn:de:0030-drops-139769},
  doi =		{10.4230/LIPIcs.CPM.2021.25},
  annote =	{Keywords: Phylogenetic tree comparison, Robinson-Foulds Distance, Optimal tree completion, Algorithms, Dynamic programming}
}

Search Results

Documents authored by Yao, Keegan

Fast Algorithms for Continuous Optimal Transport Between Histograms

Abstract

Cite as

Optimal Completion and Comparison of Incomplete Phylogenetic Trees Under Robinson-Foulds Distance

Abstract

Cite as

Thanks for your feedback!

Could not send message