Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues

DOI10.1145/3228342zbMath1454.68188OpenAlexW2270781570MaRDI QIDQ4629958

Suguru Tamaki, Yuichi Yoshida

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 programmingLasserre hierarchyordering problemgraph Laplacianexpander graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

This page was built for publication: Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues