A Note on the k-Canadian Traveller Problem

We consider the online problem k-CTP, which is the problem to guide a vehicle from some site s to some site t on a road map given by a graph G = (V,E) in which up to k (unknown) edges are blocked by avalanches. An online algorithm learns from a blocked edge when reaching one of its endpoints. Thus, it might have to change its route to the target t up to k times. We show that no deterministic online algorithm can achieve a competitive ratio smaller than 2k + 1 and give an easy algorithm which matches this lower bound. Furthermore, we show that randomization can not improve the competitive ratio substantially, by establishing a lower bound of k + 1 for the competitivity of randomized online algorithms against an oblivious adversary. Key words: routing, on-line algorithms, competitiveness