**Reference**:- Erik D. Demaine, Yamming Huang, Chung-Shou Liao, and Kunihiko Sadakane, “Canadians Should Travel Randomly”, in
*Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014)*, edited by J. Esparza, P. Fraigniaud, T. Husfeldt, and E. Koutsoupias, Lecture Notes in Computer Science, volume 8572, 2014, pages 380–391. **Abstract**:-
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 2*k*+ 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 2

*k*+ 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. **Availability**:- The paper is available in PDF (133k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- CanadianTraveler_Algorithmica (Approximating the Canadian Traveller Problem with Online Randomization)

See also other papers by Erik Demaine.

Last updated September 2, 2021 by Erik Demaine.