Paper by Erik D. Demaine

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, July 7–11, 2014, pages 380–391.

BibTeX

@InProceedings{CanadianTraveler_ICALP2014,
  AUTHOR        = {Erik D. Demaine and Yamming Huang and Chung-Shou Liao and Kunihiko Sadakane},
  TITLE         = {Canadians Should Travel Randomly},
  EDITOR        = {J. Esparza and P. Fraigniaud and T. Husfeldt and E. Koutsoupias},
  BOOKTITLE     = {Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014)},
  bookurl       = {https://icalp2014.itu.dk/},
  VOLUME        = 8572,
  SERIES        = {Lecture Notes in Computer Science},
  seriesurl     = {http://www.springer.de/comp/lncs/},
  MONTH         = {July 7--11},
  YEAR          = 2014,
  PAGES         = {380--391},

  papers        = {CanadianTraveler_Algorithmica},
  doi           = {https://dx.doi.org/10.1007/978-3-662-43948-7_32},
  dblp          = {https://dblp.org/rec/conf/icalp/DemaineHLS14},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/978-3-662-43948-7_32">SpringerLink</A>.},
}

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 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.

Comments:

This paper is also available from SpringerLink.

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)