Approximating the bandwidth via volume respecting embeddings (extended abstract)
Uriel Feige · 1998
A linear arrangement of an n-vertex graph is a one-tc+one mapping of its vertices to the integers (1,. . ., n}.The bandwidt,h of a linear arrangement is the maximum difference between mapped values of adjacent vertices.The problem of finding a linear arrangement wit,h smallest possible bandwidt,h in NP-hard.We present a randomized algorithm that runs in nearly linear time and outputs a linear arrangement whose band&dt,h is within a polylogarithmic multiplicative factor of optimal.Our algorithm is based on a new notion, called volume respecting em&tidings, which is a natural extension of small distortion embeddings of Bourgain and of Linial, London and Ra~movich.