Loading...
Please wait, while we are loading the content...
Similar Documents
Exact Algorithms for the Canadian Traveller Problem on Paths and Trees
| Content Provider | Semantic Scholar |
|---|---|
| Author | Karger, David R. Nikolova, Evdokia |
| Copyright Year | 2008 |
| Abstract | AbstractThe Canadian T raveller problem is a stochastic shortest paths problem in which one learns the costof an edge only when arriving at one of its endpoints. The goal is to nd an adapti ve polic y (adjustingas one learns more edge lengths) that minimizes the expected cost of travel. The problem is kno wn to be#P hard. Since there has been no signicant progress on approximation algorithms for several decades,we ha ve chosen to seek out special cases for which exact solutions exist, in the hope of demonstratingtechniques that could lead to further progress. Applying techniques from the theory of Mark ov DecisionProcesses, we give an exact solution for graphs of parallel (undirected) paths from source to destinationwith random tw o-v alued edge costs. W e also offer a partial generalization to traversing perfect binarytrees. MIT Computer Science & AI Lab, Cambridge MA 02139, USA, kar ger@csail.mit.eduy MIT Computer Science & AI Lab, Cambridge MA 02139, USA, enik olo va@csail.mit.edu |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://dspace.mit.edu/bitstream/handle/1721.1/40093/MIT-CSAIL-TR-2008-004.pdf?sequence=1 |
| Alternate Webpage(s) | http://people.csail.mit.edu/enikolova/papers/canadian-FINAL.pdf |
| Alternate Webpage(s) | http://dspace.mit.edu/bitstream/1721.1/40093/1/MIT-CSAIL-TR-2008-004.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
