Stanford InfoLab Publication Server

Computing Shortest Paths with Uncertainty

Feder, Tomas and Motwani, Rajeev and O'Callaghan, Liadan and Olston, Chris and Panigrahy, Rina (2003) Computing Shortest Paths with Uncertainty. Technical Report. Stanford InfoLab. (Publication Note: Twentieth International Symposium on Theoretical Aspects of Computer Science (STACS 2003))




We consider the problem of estimating the length of a shortest path in a DAG whose edge lengths are known only approximately but can be determined exactly at a cost. Initially, each edge e is known only to lie within an interval [l_e, h_e]; the estimation algorithm can pay c_e to find the exact length of e. In particular, we study the problem of finding the cheapest set of edges such that, if exactly these edges are queried, the length of the shortest path will be known, within an additive K > 0 that is given as an input parameter. We study both the general problem and several special cases, and obtain both easiness and hardness approximation results.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:shortest path, uncertainty, TRAPP
Subjects:Computer Science > Distributed Systems
Related URLs:Project Homepage
ID Code:590
Deposited By:Import Account
Deposited On:02 Dec 2002 16:00
Last Modified:24 Dec 2008 09:43

Download statistics

Repository Staff Only: item control page