Exact and Approximation Algorithms for Linear Arrangement Problems
Alain Quiliot, Djamal Rebaïne · Annals of Computer Science and Information Systems · 2014
We present here new results and algorithms for the Linear Arrangement Problem (LAP).We first propose a new lower bound, which links LAP with the Max Cut Problem, and derive a LIP model as well as a branch/bound algorithm for the general case.Then we focus on the case of interval graphs: we first show that our lower bound is tight for unit interval graphs, and derive an efficient polynomial time approximation algorithm for general interval graphs.I.