Title: Minimax Regret 1-Sink Location Problems in Dynamic Path Networks

Speaker: Yuya Higashikawa, Kyoto University

Time/Date:  Friday, April 12, 11-12
Location: Room 3402

Abstract:

We consider minimax regret 1-sink location problems in dynamic path networks.
A dynamic path network consists of an undirected path with positive
edge lengths and constant edge capacity,
and the vertex supply which is nonnegative value, called weight, is
unknown but only the interval of weight is known.
A particular realization, i.e., an assignment of weight to each
vertex, is called a scenario.
Under any scenario, the cost of a sink is defined as the minimum time
to complete evacuation for all weights,
and the regret of a sink location $x$ is defined as the cost of $x$
minus the cost of an optimal sink.
Then, the problem is to find a point as a sink such that the maximum
regret for all possible scenarios is minimized.
We present an $O(n log^2 n)$ time algorithm for minimax regret 1-sink
location problems in dynamic path networks
and show the algorithm takes $O(n)$ space, where $n$ is the number of
vertices in the network.