12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Decorous lower bounds for minimum linear arrang...
View graph of relations

« Back

Decorous lower bounds for minimum linear arrangement

Research output: Contribution to journalJournal article

Published

Journal publication date2011
JournalINFORMS Journal on Computing
Journal number1
Volume23
Number of pages15
Pages26-40
Original languageEnglish

Abstract

Minimum Linear Arrangement is a classical basic combinatorial optimization problem from the 1960s, which turns out to be extremely challenging in practice. In particular, for most of its benchmark instances, even the order of magnitude of the optimal solution value is unknown, as testified by the surveys on the problem that contain tables in which the best known solution value often has one more digit than the best known lower bound value. In this paper, we propose a linear-programming based approach to compute lower bounds on the optimum. This allows us, for the first time, to show that the best known solutions are indeed not far from optimal for most of the benchmark instances.