论文标题
多商品流量的目标位置问题
Target Location Problem for Multi-commodity Flow
论文作者
论文摘要
通过在地理分布的数据分析中进行安排的动机，我们提出了多商品流量的目标位置问题（简称LOMUF）。从其资源中发送的商品旨在定位其目标，以便从某种意义上优化了多商品流。 Lomuf是两个基本问题的组合，即设施位置问题和网络流问题。我们研究了各种环境中问题的硬度和算法问题。这些发现在三个方面。首先，获得了一系列的NP硬度和APX结果，发现解决此问题的固有困难。其次，我们提出了一种通用无向网络的近似算法和无向树的精确算法，该算法自然会在有向网络上诱导有效的近似算法。第三，我们观察到定向网络与无方向性网络之间的分离，这表明在边缘施加方向会使问题严格困难。这些结果表明了问题的丰富性，并为进一步研究铺平了道路。
Motivated by scheduling in Geo-distributed data analysis, we propose a target location problem for multi-commodity flow (LoMuF for short). Given commodities to be sent from their resources, LoMuF aims at locating their targets so that the multi-commodity flow is optimized in some sense. LoMuF is a combination of two fundamental problems, namely, the facility location problem and the network flow problem. We study the hardness and algorithmic issues of the problem in various settings. The findings lie in three aspects. First, a series of NP-hardness and APX-hardness results are obtained, uncovering the inherent difficulty in solving this problem. Second, we propose an approximation algorithm for general undirected networks and an exact algorithm for undirected trees, which naturally induce efficient approximation algorithms on directed networks. Third, we observe separations between directed networks and undirected ones, indicating that imposing direction on edges makes the problem strictly harder. These results show the richness of the problem and pave the way to further studies.
