  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 scenario. Given a scenario s and a sink location x in a dynamic
path network, let us consider the evacuation time to x of a unit supply given
on a vertex by s. The cost of x under s is defined as the sum of evacuation
times to x for all supplies given by s, and the median under s is defined as a
sink location which minimizes this cost. The regret for x under s is defined as
the cost of x under s minus the cost of the median under s. Then, the problem
is to find a sink location such that the maximum regret for all possible
scenarios is minimized. We propose an O(n^3) time algorithm for the minimax
regret 1-median problem in dynamic path networks with uniform capacity, where n
is the number of vertices in the network.
