Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
Avrim L. Blum, Goran Konjevod, R. Ravi, Santosh Vempala · 1998
We present simple semidefinite programming relaxations for the m-hard minimum bandwidth and minimum length linear ordering problems.We then show how these relaxations can be rounded in a natural way (via random projection) to obtain new approximation guarantees for both of these vertex-ordering problems.