论文标题
具有多个来源的分支最佳运输的理论和近似求解器
Theory and Approximate Solvers for Branched Optimal Transport with Multiple Sources
论文作者
论文摘要
分支最佳运输（BOT）是最佳运输的概括，在该运输中，沿边缘的运输成本是亚基的。当沿着同一路线运输质量时，该亚additivity的运输效率提高，有利于分支运输网络。在这里，我们研究了连接有限数量的源和下沉的机器人网络的NP-HARD优化，以$ \ mathbb {r}^2 $。首先，我们展示了如何有效地找到用于拓扑的许多来源和水槽的机器人网络的最佳几何形状。其次，我们认为在分支点上有超过三个边缘会议的拓扑绝不是最佳的。第三，我们表明，欧几里得平面获得的结果直接推广到二维Riemannian歧管上的最佳运输网络。最后，我们提出了一个简单但有效的近似机器人求解器，将几何优化与网络拓扑的组合优化相结合。
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 $\mathbb{R}^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.
