Abstract:
|
This paper deals with some aspects on finding good solutions
for the Minimum Linear Arrangement problem (MinLA). We consider some
random type of sparse graphs, for which it is possible to obtain
trivial constant approximations. For similar graphs, we prove that
Metropolis can find good solutions, whereas we exhibit an instance for
which Hill Climbing is expected to need an exponential number of steps
to hit an optimum. Motivated by the last results, we present an
heuristic (SS+SA) to approximate the MinLA problem on sparse
graphs. The heuristic consists in using Spectral Sequencing to obtain
a first primal solution and after improving it locally through
(Parallel) Simulated Annealing. In the last part of the paper, we
report experimental results obtained with the SS+SA heuristic when
applied to a set of large sparse geometric graphs. Compared to other
heuristics, the measurements obtained on an IBM SP2 computer with 8
processors show that the new heuristic improves the solution quality,
decreases the running time and offers an excellent speedup when ran in parallel. |