  A dynamic path network is an undirected path with evacuees situated at each
vertex. To evacuate the path, evacuees travel towards a designated sink
(doorway) to exit. Each edge has a capacity, the number of evacuees that can
enter the edge in unit time. Congestion occurs if an evacuee has to wait at a
vertex for other evacuees to leave first. The basic problem is to place k sinks
on the line, with an associated evacuation strategy, so as to minimize the
total time needed to evacuate everyone. The minmax-regret version introduces
uncertainty into the input, with the number of evacuees at vertices only being
specified to within a range. The problem is to find a universal solution whose
regret (difference from optimal for a given input) is minimized over all legal
inputs. The previously best known algorithms for the minmax regret version
problem ran in time exponential in k. In this paper, we derive new prop- erties
of solutions that yield the first polynomial time algorithms for solving the
problem.
