The Canadian Traveller Problem

Amotz Bar-Noy, Baruch Schieber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

76 Scopus citations

Abstract

Suppose that a road map is given in which each road is associated with the time it takes to traverse it. However, this road map is unreliable; some of the roads might be unsuitable for travel at certain times, and such blockage would be revealed only upon reaching an adjacent site. The Canadian Traveller Problem is to devise a travel strategy that would guarantee a good path between two sites given this uncertainty. Papadimitriou and Yannakakis proved that if the number of roads that might be blocked is not fixed, then devising a strategy that guarantees a given competitive ratio is PSPACE-complete. In this paper, we study several variations of this problem. • In the Recoverable Canadian Traveller Problem, each site is associated with a recovery time to reopen any blocked road that is adjacent to it. We present a polynomial-time travel strategy that guarantees the shortest worst-case travel time, in the case where an upper bound on the number of blockages is known in advance, and the recovery times are not long relative to the travel times. • In the stochastic variation of the Recoverable Cansidian Traveller Problem, each road is associated with an independent probability of being blocked. For this problem, we present a polynomial-time strategy that minimizes the expected travel time, in the case where the recovery times are not long relative to the travel times. • Another variation considered is the fc-Canadian Traveller Problem. Here, an upper bound, k, on the number of blocked roads is given as a parameter. We present a travel strategy that guarantees the shortest worst-case travel time. The time complexity of devising this strategy is polynomial for any constant k. On the other hand, we prove that devising such a strategy when k is non-constant is PSPACE-complete. • A "dual" problem to the Canadian Traveller Problem is the k-Vital Edges Problem. Given a road map and two specified sites, find k roads whose blockage would maximize the increase in the travel time between the two sites. We prove that this problem is NP-hard, even when the travel time of all the roads is constant. The Canadian Traveller Problem and its variations can be viewed as routing problems. In many communication networks messages routing is done according to an outdated topology of the network. Our algorithms could replace existing routing schemes to achieve more robust routing.

Original languageEnglish (US)
Title of host publicationProceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
PublisherAssociation for Computing Machinery
Pages261-270
Number of pages10
ISBN (Print)0897913760
StatePublished - Mar 1 1991
Externally publishedYes
Event2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States
Duration: Jan 28 1991Jan 30 1991

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
CountryUnited States
CitySan Francisco
Period1/28/911/30/91

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'The Canadian Traveller Problem'. Together they form a unique fingerprint.

Cite this