Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity
Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity
复制标题
DOI：
10.7155/jgaa.00336
复制
发表时间：
2014-02
期刊：
影响因子：
--
通讯作者：
Yuya Higashikawa;M. Golin;N. Katoh
中科院分区：
文献类型：
--
作者：
Yuya Higashikawa;M. Golin;N. Katoh
本文解决了动态树网络中的极小最大遗憾池位置问题。在我们的模型中，动态树网络由具有正边长度和均匀边容量的无向树组成，并且非负值的顶点供给是未知的，仅供给间隔是已知的。每个顶点的供应的特定实现称为场景。在任何场景下，某个汇点位置x的成本定义为所有补给品（疏散人员）完成疏散至x的最短时间，x的遗憾定义为x的成本减去最佳汇点位置的成本。然后，问题是找到一个汇点位置，使所有可能的情况下的最大遗憾最小化。我们提出了一种 O(n 2 log2 n) 时间算法，用于解决具有均匀容量的动态树网络中的极小最大后悔池位置问题，其中 n 是网络中的顶点数量。作为这一结果的初步步骤，我们还解决了固定场景下动态树网络中的最小成本汇位置问题，并提出了一种 O(n logn) 时间算法，如果树的边具有统一的容量，该算法将 O(n log2 n) 的现有时间限制改进了 [11]。
This paper addresses the minimax regret sink location problem in dynamic tree networks. In our model, a dynamic tree network consists of an undirected tree with positive edge lengths and uniform edge capacity, and the vertex supply which is nonnegative value is unknown but only the interval of supply is known. A particular realization of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location x is defined as the minimum time to complete the evacuation to x for all supplies (evacuees), and the regret of x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a sink location minimizing the maximum regret for all possible scenarios. We present an O(n 2 log2 n) time algorithm for the minimax regret sink location problem in dynamic tree networks with uniform capacity, where n is the number of vertices in the network. As a preliminary step for this result, we also address the minimum cost sink location problem in a dynamic tree networks under a fixed scenario and present an O(n logn) time algorithm, which improves upon the existing time bound of O(n log2 n) by [11] if edges of a tree have uniform capacity.