Experimente zum Problem der minimalen linearen Anordnung

Dieses Papier beschäftigt sich mit dem Problem der minimalen linearen Anordnung aus einer experimentellen Perspektive. Mit einer Testsuite aus spärlichen Graphen vergleichen wir experimentell mehrere Algorithmen, um obere und untere Schranken für dieses Problem zu erhalten. Die betrachteten Algorithmen umfassen heuristische Methoden zur sukzessiven Erweiterung, lokale Suchheuristiken und spektrale Sequenzierung. Die Testsuite basiert auf zwei Zufallsmodellen und "realen" Graphen. Als Ergebnis dieser Studie können zwei Hauptschlussfolgerungen gezogen werden: Einerseits werden die besten Approximationen meistens mit Simulated Annealing erzielt, was eine große Menge an Rechenzeit erfordert. Die mit spektraler Sequenzierung gefundenen Lösungen sind den mit Simulated Annealing gefundenen Lösungen ähnlich und können in deutlich weniger Zeit erreicht werden. Andererseits stellen wir fest, dass es eine große Lücke zwischen den besten oberen Schranken und den besten unteren Schranken gibt. Diese beiden Tatsachen zeigen zusammen, dass es in der Praxis schwierig ist, untere und obere Schranken für das Problem der minimalen linearen Anordnung zu finden.