Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/69694

Minimax regret 1-sink location problem in dynamic path networks

Authors Higashikawa, Yuya
Augustine, John
Cheng, Siu-Wing View this author's profile
Golin, Mordecai Jay View this author's profile
Katoh, Naoki
Ni, Guanqun
Su, Bing
Xu, Yinfeng
Issue Date 2015
Source Theoretical Computer Science , v. 588, July 2015, p. 24-36
Summary This paper considers the minimax regret 1-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths and uniform edge capacity, and each vertex supply which is non-negative value is unknown but only the interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location is defined as the minimum time to complete the evacuation for all supplies (evacuees), and the regret of a sink location x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a point as a sink such that the maximum regret for all possible scenarios is minimized. We propose an O(n logn) time algorithm for the minimax regret 1-sink location problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network. (C) 2014 Elsevier B.V. All rights reserved.
Subjects
ISSN 0304-3975
1879-2294
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Find@HKUST