Approximating the bandwidth via volume respecting embeddings
			     Uriel Feige
			  Weizmann Institute

A connected $n$-vertex graph naturally induces a metric on its
vertices, where the distance between two vertices is the length of the
shortest path connecting them. We introduce a notion of volume for
sets of vertices in graphs. We then extend the low distortion
embeddings of graphs in Euclidean space (developed by Bourgain and by
Linial, London and Rabinovich) to account not only for distances, but
also for volumes.  The usefulness of our theory of volume respecting
embeddings is demonstrated on the problem of computing the bandwidth
of a graph - a well known NP-hard problem related to efficient
manipulation of large sparse symmetric matrices.  We develop a
randomized algorithm that runs in slightly superlinear time and
approximates the bandwidth within factors of $(\log n)^{O(1)}$.
Previously, even an approximation ratio of $n^{1-\epsilon}$ was not
known to be achievable for this problem.  Our algorithm was
implemented and preliminary experimental results are available.