We study online algorithms for the Canadian Traveller Problem (CTP)
introduced by Papadimitriou and Yannakakis in 1991. In this problem, a
traveller knows the entire road network in advance, and wishes to travel as
quickly as possible from a source vertex s to a destination vertex
t, but discovers online that some roads are blocked (e.g., by snow)
once reaching them. It is PSPACE-complete to achieve a bounded competitive
ratio for this problem. Furthermore, if at most k roads can be
blocked, then the optimal competitive ratio for a deterministic online
algorithm is 2k + 1, while the only randomized result known
is a lower bound of k + 1.
In this paper, we show for the first time that a polynomial time randomized
algorithm can beat the best deterministic algorithms, surpassing the
2k + 1 lower bound by an o(1) factor. Moreover, we
prove the randomized algorithm achieving a competitive ratio of
(1 + √2/2) k + 1
in pseudo-polynomial time. The proposed techniques can also be applied to
implicitly represent multiple near-shortest s-t paths.