An optimal randomized online algorithm for the -Canadian Traveller Problem on node-disjoint paths

摘要

We consider the -Canadian Traveller Problem, which asks for a shortest path between two nodes and in an undirected graph, where up to edges may be blocked. An online algorithm learns about a blocked edge when reaching one of its endpoints. Recently, it has been shown that no randomized online algorithm can be better than -competitive, even if all --paths are node-disjoint. We show that the bound is tight by constructing a randomized online algorithm for this case that achieves the ratio against an oblivious adversary and is therefore best possible.