Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
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
Quelle
SpringerLink (Online service)
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.