• 
• 
• 
• 
• 
• 

Stochastic Routing

We are developing optimal routing algorithms for networks where the costs vary probabilistically.

Background & Objective:  We study real-world networks such as traffic, communications, and logistics. In these settings, advancing a link is not a sure thing: The cost, time, and success will vary probabilistically. Classical routing algorithms can yield catastrophically bad outcomes. We are developing methods to optimize various measures of performance and bound the probability of failure.

Technical Discussion:  We optimize expected utility where the user's utility is some nonlinear function of the realized total travel time or cost. We have proven that some such optimizations are NP-hard and/or inapproximable. For other useful cases we have found very efficient algorithms and approximation schemes. Two examples that are especially suitable for current car-navi hardware: Choosing a route that maximizes the probability of arriving before a deadline, and choosing a policy that minimizes time and avoids jams when the congestion state of the whole network changes stochastically.

Publications:
Nikolova, E.; Kelner, J.; Brand, M.; Mitzenmacher,M., "Stochastic Shortest Paths Via Quasi-convex Maximization", ESA 2006, ISBN:3-540-38875-3, Pp 552 - 563 , September 2006 (ACM Portal, TR2006-128)

Nikolova, E.; Brand, M.; Karger, D.R., "Optimal Route Planning under Uncertainty", International Conference on Automated Planning and Scheduling (ICAPS), June 2006 (ICAPS 2006, TR2006-060)

Technology Area:  Algorithms

Modification Date:  January 16, 2009