The Canadian Traveller Problem on outerplanar graphs

-- Pierre Bergé (LIMOS)

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.

Category: seminars
Tags: Team seminar networks