Computing Shortest Paths with Uncertainty

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.