| y (2007) | |||||||||||||||
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. We obtain both positive and negative results on both the exact problem and its approximation. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||