(Professor Satish Rao)

A recent result by Harald Räcke [1] gives an oblivious algorithm for routing a flow in a general graph G=(V,E) with polylogarithmic (in V) congestion over the optimal set of routes. He does this by showing there exists an embedding of any graph into a tree, T(G), and that routing any flow on T(G) is no worse than routing the same flow on G. In addition, he also embeds T(G) on to G and shows that it is possible to route on G with only polylogarithmically more congestion than on T(G). Räcke, however, does not give a polynomial-time algorithm for constructing the embedding.

We have several goals related to this. First, we seek to give a polynomial-time construction of an embedding that can be used this way, and hope that such a construction will give lead to a simpler proof of his result.

Second, we wish to find, in general, the cost of an oblivious
algorithm. While Räcke's result shows that the gap between the best
oblivious algorithm and the best non-oblivious algorithm is polylog(n)
for the general case, this may not be tight, and the gap may even be
constant when all the messages have a single source or single
destination. The gap may be larger if the graph is allowed to have
*directed* edges.

- [1]
- H. Räcke, "Minimizing Congestion in General Networks,"
*Proc. Symp. Foundations of Computer Science,*Vancouver, Canada, November 2002.

(Professor Satish Rao)

Given a set of points, S, in a metric space and query point q, the goal is to find the point in S closest to q. Ideally, the data structure to do this only relies on an oracle that gives the distance between any two points, and not on any other detail of the metric space.

In some metric spaces, this seems difficult. Consider, for example, a metric space and a query point such that all points in S are at a distance one from each other, and all but one are at distance q from S. Finding the one point closest to q will probably require querying the distance from q to every point in S. In other metric spaces, it is possible to do this with a logarithmic number of queries (see [1] or [2]).

Following up on [1] and [2], we have a result showing that this can be done in constant space and logarithmic time for unchanging sets S and hope to argue that a similar data structure with expected constant space works for dynamic sets S.

A more general goal is to characterize the metric spaces for which finding the nearest point requires a sublinear number of queries and develop algorithms for those metric spaces.

- [1]
- K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao, "Distributed Object Location in a Dynamic Network,"
*Proc. ACM Symp. Parallel Algorithms and Architectures,*Winnepeg, Canada, August 2002. - [2]
- D. Karger and M. Ruhl, "Finding Nearest Neighbors in Growth-Restricted Metrics,"
*Proc. ACM Symp. Theory of Computing,*Montreal, Canada, May 2002.