The Canadian Traveller Problem
Amotz Bar-Noy, Baruch Schieber · Symposium on Discrete Algorithms · 1991
Suppose that a road map is given in which each road is associated with the time it takes to traverse it. However, this road map is unreliable; some of the roads might be unsuitable for travel at certain times, and such blockage would be revealed only upon reaching an adjacent site. The Canadian Traveller Problem is to devise a travel strategy that would guarantee a good path between two sites given this uncertainty. l?apadirnitriou and Yannakakis proved that if the number of roads that might be blocked is not fixed, then devising a strategy that guarantees a given competitive ratio is PSPACEcompIete. In this paper, we study several variations of this problem.