Paper by Erik D. Demaine

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.

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.

The paper is available in PDF (133k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated May 17, 2017 by Erik Demaine.