Article ID Journal Published Year Pages File Type
6874759 Journal of Discrete Algorithms 2017 9 Pages PDF
Abstract
We develop a series of theorems about the graph structure of the classical Minimum Linear Arrangement (MinLA) problem which disclose properties that can be exploited by Multi-Neighborhood Search (MNS) algorithms. As a foundation, we differentiate between swaps of labels attached to adjacent and non-adjacent nodes to create two new neighborhood classes, and show how our theorems yield efficient algorithms for updating key arrays used by local search procedures. In addition, we introduce a class of neighborhoods called set-based neighborhoods supported by a theorem that identifies solutions (labelings) for the MinLA problem in polynomial time that dominate exponential numbers of alternative solutions. The component neighborhoods within this new neighborhood class can be applied in various sequences in conjunction with the first two new neighborhoods introduced. Our results also apply to problems with objectives different than those of MinLA. Finally, our results make it possible to exploit the new neighborhoods according to the user's choice of MNS protocols and alternative local search algorithms.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,