Decorous Lower Bounds for Minimum Linear Arrangement

Decorous Lower Bounds for Minimum Linear Arrangement

0.00 Avg rating0 Votes
Article ID: iaor20112495
Volume: 23
Issue: 1
Start Page Number: 26
End Page Number: 40
Publication Date: Dec 2011
Journal: INFORMS Journal on Computing
Authors: , ,
Keywords: programming: linear
Abstract:

Minimum linear arrangement is a classical basic combinatorial optimization problem from the 1960s that 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.

Reviews

Required fields are marked *. Your email address will not be published.