Exact Algorithms for the Canadian Traveller Problem on Paths and Trees

The Canadian Traveller problem is a stochastic shortest paths problem in which one learns the cost of an edge only when arriving at one of its endpoints. The goal is to find an adaptive policy (adjusting as one learns more edge lengths) that minimizes the expected cost of travel. The problem is know...

Full description

Bibliographic Details
Main Authors: Karger, David, Nikolova, Evdokia
Other Authors: David Karger
Published: 2008
Subjects:
Online Access:http://hdl.handle.net/1721.1/40093