  This study examines the time complexities of the unbalanced optimal transport
problems from an algorithmic perspective for the first time. We reveal which
problems in unbalanced optimal transport can/cannot be solved efficiently.
Specifically, we prove that the Kantorovich Rubinstein distance and optimal
partial transport in the Euclidean metric cannot be computed in strongly
subquadratic time under the strong exponential time hypothesis. Then, we
propose an algorithm that solves a more general unbalanced optimal transport
problem exactly in quasi-linear time on a tree metric. The proposed algorithm
processes a tree with one million nodes in less than one second. Our analysis
forms a foundation for the theoretical study of unbalanced optimal transport
algorithms and opens the door to the applications of unbalanced optimal
transport to million-scale datasets.
