Loading...
Loading...

Go to the content (press return)

Heuristics for the MinLA problem: some theoretical and empirical considerations

Author
Diaz, J.; Petit, J.; Spirakis, P.G.; Serna, M.
Type of activity
Report
Date
1998-03
Code
LSI-98-15-R
Repository
http://hdl.handle.net/2117/96970 Open in new window
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 appr...
Citation
Diaz, J., Petit, J., Spirakis, P.G., Serna, M. "Heuristics for the MinLA problem: some theoretical and empirical considerations". 1998.
Keywords
Heuristics, MinLA, Minimum linear arrangement, SS+SA
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

Attachments