Notice
This is not the latest version of this item. The latest version can be found at:https://dspace.mit.edu/handle/1721.1/136731.2
Approximating the Canadian Traveller Problem with Online Randomization
Author(s)
Demaine, Erik D; Huang, Yamming; Liao, Chung-Shou; Sadakane, Kunihiko
Download453_2020_792_ReferencePDF.pdf (943.5Kb)
Open Access Policy
Open Access Policy
Creative Commons Attribution-Noncommercial-Share Alike
Terms of use
Metadata
Show full item recordAbstract
Abstract
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
$$2k+1$$
2
k
+
1
, while the only randomized result known so far is a lower bound of
$$k+1$$
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
$$2k+1$$
2
k
+
1
by an o(1) factor. Moreover, we prove that the randomized algorithm can achieve a competitive ratio of
$$\big (1+ \frac{\sqrt{2}}{2} \big )k + \sqrt{2}$$
(
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.
Date issued
2021-01-08Publisher
Springer US
Citation
Demaine, Erik D, Huang, Yamming, Liao, Chung-Shou and Sadakane, Kunihiko. 2021. "Approximating the Canadian Traveller Problem with Online Randomization."
Version: Author's final manuscript