Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 2

Proceedings of the 2014 Federated Conference on Computer Science and Information Systems

Exact and Approximation Algorithms for Linear Arrangement Problems

Alain Quiliot, Djamal Rebaine

DOI: http://dx.doi.org/10.15439/2014F50

Citation: Proceedings of the 2014 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 2, pages 493–500 (2014)

Full text

Abstract. 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.