Kombinatorische Optimierung

Vielen Problemen der Optimierung und der Informatik liegen diskrete Strukturen zugrunde, über die für lineare oder nichtlineare Funktionen ein Optimum bestimmt werden soll. In Projekten der kombinatorischen Optimierung werden diese Probleme zunächst hinsichtlich ihrer Komplexität charakterisiert. Danach wird versucht, effiziente Algorithmen zu entwickeln, wobei - abhängig von der Komplexität des Problems - exakte, approximative oder randomisierte Algorithmen relevant werden.

Ihre herausragende Bedeutung in den letzten Jahren verdankt die kombinatorische Optimierung vor allem der Verschiedenartig- und Wichtigkeit vieler ihrer Anwendungsgebiete. Viele Entscheidungssituationen, wie sie etwa in Industrie und Wirtschaft auftreten, lassen sich auf natürliche Weise als ganzzahlig-lineare Optimierungsprobleme über endlichen, allerdings meist astronomisch großen Mengen formulieren. Tiefergehendes theoretisches Verständnis der zugrundeliegenden mathematischen Struktur des Lösungsraumes ermöglicht vielfach die Entwicklung beweisbar ,,guter`` und in der Praxis erfolgreicher Algorithmen.

Dieses Kapitel veranschaulicht sowohl beispielhaft anwendungsbezogene Aspekte kombinatorischer Techniken als auch theoretische Forschungsergebnisse unserer Arbeitsgruppe.