A Hierarchical Approach to Optimal Transport
A Hierarchical Approach to Optimal Transport
复制标题
优化运输的分层方法
DOI：
10.1007/978-3-642-38267-3_38
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
C. Schnörr
中科院分区：
文献类型：
--
作者：
Schmitzer;C. Schnörr
一类重要的变分模型与匹配一般数据结构和度量度量空间的比较有关，导致计算密集的密集线性分配和质量运输问题。为了加快计算速度，我们提出了对拍卖算法的扩展，利用了其他任意成本函数的规律性。该算法仅考虑可能分配对的稀疏子集，同时仍保证解的全局最优性。这些子集由多尺度方法和层次一致性检查确定，以便在连续更细的尺度上解决问题。虽然理论上的最坏情况复杂性是有限的，但在各种实际实验场景中观察到的平均情况复杂性在计算时间上产生了显著的增益，并且随着问题规模的增加而增加。
A significant class of variational models in connection with matching general data structures and comparison of metric measure spaces, lead to computationally intensive dense linear assignment and mass transportation problems. To accelerate the computation we present an extension of the auction algorithm that exploits the regularity of the otherwise arbitrary cost function. The algorithm only takes into account a sparse subset of possible assignment pairs while still guaranteeing global optimality of the solution. These subsets are determined by a multiscale approach together with a hierarchical consistency check in order to solve problems at successively finer scales. While the theoretical worst-case complexity is limited, the average-case complexity observed for a variety of realistic experimental scenarios yields a significant gain in computation time that increases with the problem size.