An optimal randomized online algorithm for the \(k\)-Canadian Traveller Problem on node-disjoint paths
We consider the \(k\)-Canadian Traveller Problem, which asks for a shortest path between two nodes \(s\) and \(t\) in an undirected graph, where up to \(k\) 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 \((k+1)\)-competitive, even if all \(s\)-\(t\)-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.
online algorithm competitive analysis canadian traveller problem