next up previous contents
Next: Clustern durch Baumzerlegungen Up: Vehicle Routing Probleme Previous: Vehicle Routing Probleme

Komplexitätstheoretische Resultate

Erste Resultate waren ein allgemeiner NP-Vollständigkeitsbeweis und ein heuristischer Greedyansatz, der als Verallgemeinerung des von Kundu und Misra vorgeschlagenen Verfahrens zur Zerlegung von Bäumen mit einer Gewichtsfunktion aufgefaßt werden kann. Detailliertere Auseinandersetzungen mit dem Problem, den Praxisdaten und den NP-Vollständigkeitsbeweisen ergaben eine Unterscheidung der Baumzerlegungsprobleme sowohl nach dem Knotengrad der untersuchten Bäume als auch nach der Anzahl der Gewichtsfunktionen. Unter diesen Gesichtspunkten konnten wir eine vollständige Klassifizierung des Baumzerlegungsproblems unter Nebenbedingungen angeben:

NP-vollständig im strengen Sinne ist das Baumzerlegungsproblem für Instanzen, bei denen die Anzahl der Gewichtsfunktionen mit der Problemgröße wächst. Bei Bäumen mit mindestens zwei Gewichtsfunktionen und unbeschränktem Knotengrad wird die Fragestellung zu einem Number-Problem. Es gelang uns hier, das Knapsack-Problem auf diese Teilklasse zu reduzieren und durch Angabe eines dynamischen Programmes die Pseudopolynomialität nachzuweisen. Bei Probleminstanzen mit einer Gewichtsfunktion ist der von Kundu und Misra beschriebene lineare Greedy-Algorithmus optimal. Für den bei der Clusterung auftretenden praxisrelevanten Fall der Zerlegung knotengradbeschränkter Bäume mit einer beschränkten Anzahl von Gewichtsfunktionen konnten wir ein exaktes polynomielles Verfahren entwickeln, das auf den Ideen des Greedy-Ansatzes aufbaut.



Webmaster<www@zpr.uni-koeln.de>
1999-07-28