The Canadian Traveller Problem on outerplanar graphs
Time: 14:15 -- Location: LRI, 445
summary: We focus on the PSPACE-complete k-Canadian Traveller Problem, where a weighted graph
with a source s and a target t are given. This problem also has a hidden input of cardinality
at most k representing blocked edges. The objective is to travel from s to t with the minimum
distance. At the beginning of the walk, the blockages are unknown: the traveller discovers that
an edge is blocked when visiting one of its endpoints. Online algorithms, also called strategies,
have been proposed for this problem and assessed with the competitive ratio.
Even though the optimal competitive ratio is 2k+1 even on unit-weighted planar graphs of treewidth 2,
we design a polynomial-time strategy achieving competitive ratio 9 on unit-weighted outerplanar graphs.
This value 9 also stands as a lower bound for this family of graphs. Finally, we show that it is not
possible to achieve a constant competitive ratio (independent of G and k) on arbitrarily-weighted
outerplanar graphs.