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

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

0.00 Avg rating0 Votes
Article ID: iaor201526108
Volume: 30
Issue: 1
Start Page Number: 87
End Page Number: 96
Publication Date: Jul 2015
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: graphs, heuristics
Abstract:

We consider the k equ1 ‐Canadian Traveller Problem, which asks for a shortest path between two nodes s equ2 and t equ3 in an undirected graph, where up to k equ4 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 ) equ5 ‐competitive, even if all s equ6 t equ7 ‐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.

Reviews

Required fields are marked *. Your email address will not be published.