On Euclidean Embeddings and Bandwidth Minimization

Lecture notes in computer sciencePublished 1 January 2001

John Dunagan, Santosh Vempala

DOI10.1007/3-540-44666-4_26

Source URL

Citations43

SJR quartileQ2

SJR score0.35

SNIP0.55

TL;DR

Euclidean embeddings of Euclidean metrics are studied to present an O(log3 n√log log n) approximation for minimum bandwidth in conjunction with a semi-definite relaxation and a lower bound on the least possible volume distortion for Euclidan metrics.

Abstract

We study Euclidean embeddings of Euclidean metrics and present the following four results: (1) an O(log3 n√log log n) approximation for minimum bandwidth in conjunction with a semi-definite relaxation, (2) an O(log3 n) approximation in O(n log n ) time using a new constraint set, (3) a lower bound of Θ(√log n) on the least possible volume distortion for Euclidean metrics, (4) a new embedding with O(√log n) distortion of point-to-subset distances.

Keywords

Computer Science

Israel Journal of MathematicsOn lipschitz embedding of finite metric spaces in Hilbert space

545 Citations1985Jean Bourgain

ComputingThe NP-Completeness of the bandwidth minimization problem

407 Citations1976Ch. H. Papadimitriou

The Problem of minimizing the bandwidth of the nonzero entries of a sparse symmetric matrix by permuting its rows and columns and some related combinatorial problems are shown to be NP-Complete.

Small distortion and volume preserving embeddings for planar and Euclidean metrics

198 Citations1999Satish Rao

The results give improvements for Feige's and Vempala’s approximation algorithms for planar and Euclidean metrics and an improved bound for volume respecting embeddings for Euclidan metrics.

View PDF

Journal of Computer and System SciencesApproximating the Bandwidth via Volume Respecting Embeddings

142 Citations2000Uriel Feige

A randomized algorithm that runs in nearly linear time and outputs a linear arrangement whose bandwidth is within a polylogarithmic multiplicative factor of optimal, based on a new notion, called volume respecting embeddings.

Random projection: a new approach to VLSI layout

49 Citations2002S. Vempala

It is shown that random projection, the technique of projecting a set of points to a randomly chosen low-dimensional subspace, can be used to solve problems in VLSI layout and an O(log/sup 3.5/ n) approximation algorithm is obtained, which is the first o(n) approximation.

Approximating the bandwidth via volume respecting embeddings (extended abstract)

41 Citations1998Uriel Feige

A randomized algorithm is presented that runs in nearly linear time and outputs a linear arrangement whose band-widt,h is within a polylogarithmic multiplicative factor of optimal.

View PDF

Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems

39 Citations1998Avrim Blum, Goran Konjevod +2 more

It is shown how these relaxations can be rounded in a natural way (via random projection) to obtain approximation guarantees for both the NP-hard minimum bandwidth and minimum length linear ordering problems.

View PDF