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.