[ Pagewise preview ]
| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/2003-2 | ||
| Submitted on | 3rd of December 2002 | ||
| Author | Feder, Tomas; Motwani, Rajeev; O'Callaghan, Liadan; Olston, Chris; Panigrahy, Rina | ||
| Title | Computing Shortest Paths with Uncertainty | ||
| Date of publication | February 2003 | ||
| Published in | Proceedings of the Twentieth International Symposium on Theoretical Aspects of Computer Science (STACS 2003) | ||
| Citation | Feder, Tomas; Motwani, Rajeev; O'Callaghan, Liadan; Olston, Chris; Panigrahy, Rina. Computing Shortest Paths with Uncertainty, Proceedings of the Twentieth International Symposium on Theoretical Aspects of Computer Science (STACS 2003) | ||
| Number of pages | 12 | ||
| Language | English | ||
| Project | TRAPP | ||
| Type | Conference or Journal Paper | ||
| Subject group | Distributed Systems | ||
| 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. | ||
| Keywords | shortest path, uncertainty, TRAPP | ||
| Contact address | olston@db.stanford.edu | ||
| Fulltext source |
| Management of the document by | siroker@db.stanford.edu
| |
[ Pagewise preview ]