Approximating the Bandwidth Via Volume Respecting Embeddings

Résumé du livre

Abstract: "A linear arrangement of an n-vertex graph is a one-to-one mapping of its vertices to the integers [1 ..., n]. The bandwidth of a linear arrangement is the maximum difference between mapped values of adjacent vertices. The problem of finding a linear arrangement with smallest possible bandwidth in [sic] NP-hard. We present a randomized algorithm that runs in nearly linear time and outputs a linear arrangement whose bandwidth is within a polylogarithmic multiplicative factor of optimal. Our algorithm is based on a new notion, called volume respecting embeddings, which is a natural extension of small distortion embeddings of Bourgain and of Linial, London and Rabinovich."