Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues

DOI10.1145/3228342zbMath1454.68188MaRDI QIDQ4629958

Yuichi Yoshida, Suguru Tamaki

Publication date: 28 March 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3228342

zbMATH Keywords

semidefinite programming; Lasserre hierarchy; ordering problem; graph Laplacian; expander graph

Mathematics Subject Classification ID

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

68W20: Randomized algorithms