T. Feder, R. Motwani, C. Olston, R. Panigrahy
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...
Balanced Allocation on Graphs (2005)
In this paper, we study the two choice balls and bins process when balls are not allowed to choose any two random bins, but only bins that are connected by an edge in an underlying graph. We show...
Representing graph metrics with fewest edges (2003)
Adam Meyerson, R. Motwani, R. Panigrahy
Abstract We consider the problem of obtaining compressed representations for graph metrics by adding extra ("Steiner") vertices and removing edges, while preserving distances. The...
Computing shortest paths with uncertainty (2003)
T. Feder, R. Motwani, C. Olston, R. Panigrahy
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...
Computing shortest paths with uncertainty (2003)
T. Feder, R. Motwani, C. Olston Y, R. Panigrahy
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...