Exact and approximation algorithms for Linear Arrangement Problems

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.