Theory and Approximate Solvers for Branched Optimal Transport with Multiple Sources

Abstract:

Branched Optimal Transport (BOT) is a generalization of optimal transport in which transportation costs along an edge are subadditive. This subadditivity models an increase in transport efficiency when shipping mass along the same route, favoring branched transportation networks. We here study the NP-hard optimization of BOT networks connecting a finite number of sources and sinks in ℝ2. First, we show how to efficiently find the best geometry of a BOT network for many sources and sinks, given a topology. Second, we argue that a topology with more than three edges meeting at a branching point is never optimal. Third, we show that the results obtained for the Euclidean plane generalize directly to optimal transportation networks on two-dimensional Riemannian manifolds. Finally, we present a simple but effective approximate BOT solver combining geometric optimization with a combinatorial optimization of the network topology.

SEEK ID: https://publications.h-its.org/publications/1689

DOI: 10.48550/arXiv.2210.07702

Research Groups: SIMPLAIX

Publication type: Journal

Journal: arXiv,cs.LG,2210.07702

Citation: arXiv,cs.LG,2210.07702

Date Published: 2022

URL:

Registered Mode: imported from a bibtex file

Authors: Peter Lippmann, Enrique Fita Sanmartín, Fred A. Hamprecht

Citation
Lippmann, P., Sanmartín, E. F., & Hamprecht, F. A. (2022). Theory and Approximate Solvers for Branched Optimal Transport with Multiple Sources (Version 1). arXiv. https://doi.org/10.48550/ARXIV.2210.07702
Activity

Views: 1275

Created: 4th Aug 2023 at 10:14

Last updated: 5th Mar 2024 at 21:25

help Tags

This item has not yet been tagged.

help Attributions

None

Powered by
(v.1.14.2)
Copyright © 2008 - 2023 The University of Manchester and HITS gGmbH