Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity

Yuya Higashikawa, Mordecai J. Golin, Naoki Katoh

doi:10.1007/978-3-319-04657-0_14

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.

Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity

書誌事項

この論文をさがす

説明

収録刊行物

被引用文献 (10)*注記

関連プロジェクト

詳細情報詳細情報について

書き出し

問題の指摘

Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity

書誌事項

この論文をさがす

説明

収録刊行物

被引用文献 (10)*注記

関連プロジェクト

詳細情報 詳細情報について

書き出し

問題の指摘

詳細情報詳細情報について