TY - GEN
T1 - The Canadian Traveller Problem
AU - Bar-Noy, Amotz
AU - Schieber, Baruch
N1 - Publisher Copyright:
© 1991 Association for Computing Machinery. All rights reserved.
PY - 1991/3/1
Y1 - 1991/3/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85024370436&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85024370436&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85024370436
SN - 0897913760
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 261
EP - 270
BT - Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
PB - Association for Computing Machinery
T2 - 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
Y2 - 28 January 1991 through 30 January 1991
ER -