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))

BibTeX | DublinCore | EndNote | HTML |

| PDF 194Kb |

## Abstract

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 | |

Projects: | TRAPP | |

Related URLs: | Project Homepage | http://infolab.stanford.edu/trapp/ |

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