Steiner et al.

Für unsere Untersuchungen zu NP-schweren Problemen haben wir uns das Steinerbaumproblem herausgesucht:

Steinerbäume bilden wegen ihrer kürzeren Gesamtkantenlänge eine attraktive Alternative zu herkömmlichen aufspannenden Bäumen. Leider ist das Problem, einen minimalen Steinerbaum zu finden (im Gegensatz zu dem Problem, einen minimalen aufspannenden Baum zu finden) NP-schwer; dies gilt sogar für scheinbar einfache Spezialfälle, wie z.B. bei Verwendung der Manhattan-Metrik.

Nachdem wir in früheren Jahren schnelle Heuristiken entwickelt haben, die dem Optimum sehr nahe kommen (ca. 25%), haben wir uns in der jüngeren Vergangenheit auf die Entwicklung von Algorithmen spezialisiert, die für kleinere Probleminstanzen das Optimum exakt berechnen; dabei haben wir einen Weltrekord aufgestellt -- unser Verfahren löst jedes Problem bis zur Größe von 55 Punkten und viele größere Probleme bis zu 100 Punkten.

• M. Kaufmann, S. Gao, K. Thulasiraman: "On Steiner Minimal Trees in Grid Graphs and its Application to Homotopic Routing", Journal of Circuits, Systems and Computers, Vol. 6, No. 1, pp. 1-13, 1996.
• P. Berman, U. Fößmeier, M. Karpinski, M. Kaufmann, A. Zelikovsky: "Approaching the 5/4 -- Approximation for Rectilinear Steiner Trees", Proc. 2nd European Symposium on Algorithms (ESA '94), LNCS, Springer Verlag, pp. 60-71, 1994.
• U. Fößmeier, M. Kaufmann, A. Zelikovsky: "Faster Approximation Algorithms for the Rectilinear Steiner Problem", Discrete & Computational Geometry 18, pp. 93-109, 1997.
• U. Fößmeier and M. Kaufmann: "Solving Rectilinear Steiner Tree Problems Exactly in Theory and Practice", Proc. 5th European Symposium on Algorithms (ESA '97), LNCS 1284, Springer Verlag, pp. 171-185, 1997.