Name
Abstract | ||
|---|---|---|
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 nonnegative 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 log ¿ n ) 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.tcs.2014.02.010 | Theoretical Computer Science |
Keywords | Field | DocType |
Minimax regret,Sink location,Dynamic flow,Evacuation planning | Mathematical optimization,Regret,Vertex (geometry),Minimum time,Sink (computing),Mathematics | Journal |
Volume | Issue | ISSN |
588 | C | 0304-3975 |
Citations | PageRank | References |
9 | 0.66 | 13 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuya Higashikawa | 1 | 64 | 12.71 |
| John Augustine | 2 | 205 | 24.35 |
| Siu-Wing Cheng | 3 | 973 | 94.74 |
| Mordecai J. Golin | 4 | 767 | 89.67 |
| naoki katoh | 5 | 1101 | 187.43 |
| Guanqun Ni | 6 | 39 | 6.60 |
| Bing Su | 7 | 17 | 4.72 |
| Yinfeng Xu | 8 | 1636 | 108.18 |