Minmax-Regret Evacuation Planning for Cycle Networks.

This paper considers the problem of evacuating people located at vertices to a “sink” in a cycle network. In the “minmax-regret” version of this problem, the exact number of evacuees at each vertex is unknown, but only an interval for a possible number is given. We show that a minmax-regret 1-sink in cycle networks with uniform edge capacities can be found in \(O(n^2)\) time, where n is the number of vertices. No correct algorithm was known before for this problem.