Name
Abstract | ||
|---|---|---|
This paper considers the minimax regret 1-median problem in dynamic path networks. In our model, we are given a dynamic path network consisting of an undirected path with positive edge lengths, uniform positive edge capacity, and nonnegative vertex supplies. Here, each vertex supply is unknown but only an interval of supply is known. A particular assignment of supply to each vertex is called a . Given a scenario and a sink location in a dynamic path network, let us consider the evacuation time to of a unit supply given on a vertex by . The cost of under is defined as the sum of evacuation times to for all supplies given by , and the under is defined as a sink location which minimizes this cost. The regret for under is defined as the cost of under minus the cost of the median under . Then, the problem is to find a sink location such that the maximum regret for all possible scenarios is minimized. We propose an ( ) time algorithm for the minimax regret 1-median problem in dynamic path networks with uniform capacity, where is the number of vertices in the network. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00224-017-9783-8 | Theory Comput. Syst. |
Keywords | DocType | Volume |
minimax regret,Sink location,Dynamic flow,Evacuation planning | Journal | 62 |
Issue | ISSN | Citations |
6 | 1432-4350 | 1 |
PageRank | References | Authors |
0.40 | 12 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuya Higashikawa | 1 | 64 | 12.71 |
| Siu-Wing Cheng | 2 | 973 | 94.74 |
| Tsunehiko Kameda | 3 | 282 | 35.33 |
| naoki katoh | 4 | 1101 | 187.43 |
| shun saburi | 5 | 1 | 0.40 |