Details

Autor(en) / Beteiligte

• Demaine, Erik D.
• Huang, Yamming
• Liao, Chung-Shou
• Sadakane, Kunihiko

Titel

Approximating the Canadian Traveller Problem with Online Randomization

Ist Teil von

• Algorithmica, 2021-05, Vol.83 (5), p.1524-1543

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2021

Link zum Volltext

Quelle

SpringerLink

Beschreibungen/Notizen

• In this paper, we study online algorithms for the Canadian Traveller Problem defined by Papadimitriou and Yannakakis in 1991. This problem involves a traveller who 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. Achieving a bounded competitive ratio for the problem is PSPACE-complete. Furthermore, if at most k roads can be blocked, the optimal competitive ratio for a deterministic online algorithm is 2 k + 1 , while the only randomized result known so far is a lower bound of k + 1 . We show, for the first time, that a polynomial time randomized algorithm can outperform the best deterministic algorithms when there are at least two blockages, and surpass the lower bound of 2 k + 1 by an o (1) factor. Moreover, we prove that the randomized algorithm can achieve a competitive ratio of ( 1 + 2 2 ) k + 2 in pseudo-polynomial time. The proposed techniques can also be exploited to implicitly represent multiple near-shortest s - t paths.