Roads in Canada often get blocked due to excessive snowfall during blizzards. On encountering a road closure, a driver needs to adapt their route on-the-fly (possibly involving backtracking) in order to minimise the time taken to reach their destination. This problem is known as the Canadian traveller problem.
Formally, given a graph with partially observable edge weights, the goal is to synthesise a strategy that minimises the total weight of a walk to the target vertex, where an edge weight is only learnt on visiting an endpoint of the edge. We look at two different variants of this problem:
- [PY91] The edge weights are chosen by an adversary. We want a strategy with the best competitive ratio, that is, one that minimises the ratio of the total weight of the walk taken to that of the total weight of the walk given by an optimal offline algorithm.
- [KN07] The edge weights are given by a probability distribution. We want a strategy that minimises the expected total weight of a walk to the destination.
References:
- [PY91](https://www.sciencedirect.com/science/article/pii/0304397591902632) Christos Papadimitriou and Mihalis Yannakakis, Shortest paths without a map (1991)
- [KN07](https://people.csail.mit.edu/enikolova/papers/canadian-FINAL.pdf) David Karger and Evdokia Nikolova, Exact Algorithms for the Canadian Traveller Problem on Paths and Trees (2007)
