Approximation heuristics and benchmarkings for the MinLA problem
Jordi Petit · 1997
This paper presents heuristic approximation algorithms and methods to find lower bounds to approximate the Minimum Linear Arrangement problem and evaluates and compares experimentaly their behaviour when they are applied to sparse graphs. The low number of theoretical results for this problem motivates its experimental study. The algorithms presented and analyzed belong to the families of Successive Augmentation algorithms (also called greedy algorithms), local search algorithms (Hillclimbing, Metropolis and Simulated Annealing) and Spectral Sequencing. The empirical results are based on two random models and "real life" graphs. The conclusion is that the best approximations are obtained using Simulated Annealing, which involves a large amount of computation time. However, solutions found by Spectral Sequencing are also good and can be found in radically less time. We remark that the performance of the algorithms heavily depends on the kind of graph. 1 Introduction and basic results G...