Approximating the Bandwidth via Volume Respecting Embeddings
Approximating the Bandwidth via Volume Respecting Embeddings
复制标题
通过体积尊重嵌入来近似带宽
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
U. Feige
中科院分区：
文献类型：
--
作者：
U. Feige
N-顶点图的线性排列是其顶点到整数{1，？，n}的一对一映射。线性排列的带宽是相邻顶点的映射值之间的最大差值。寻找具有最小可能带宽的线性排列的问题是NP困难的。我们提出了一种随机化算法，它运行在近乎线性的时间内，并输出带宽在最优的多对数乘数内的线性排列。我们的算法基于一个新的概念，称为体积尊重嵌入，它是Bourain以及Linial，London和Rabinovich的小失真嵌入的自然扩展。
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 is 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.