A note on the k-Canadian Traveller Problem

A note on the k-Canadian Traveller Problem

0.00 Avg rating0 Votes
Article ID: iaor20091363
Country: Netherlands
Volume: 106
Issue: 3
Start Page Number: 87
End Page Number: 89
Publication Date: Apr 2008
Journal: Information Processing Letters
Authors:
Keywords: computational analysis, programming: travelling salesman
Abstract:

We consider the online problem k-CTP, which is the problem to guide a vehicle from some site s to some site t on a road map given by a graph G=(V,E) in which up to k (unknown) edges are blocked by avalanches. An online algorithm learns from a blocked edge when reaching one of its endpoints. Thus, it might have to change its route to the target t up to k times. We show that no deterministic online algorithm can achieve a competitive ratio smaller than 2k+1 and give an easy algorithm which matches this lower bound. Furthermore, we show that randomization can not improve the competitive ratio substantially, by establishing a lower bound of k+1 for the competitivity of randomized online algorithms against an oblivious adversary.

Reviews

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