Forschungsinstitut für Diskrete Mathematik

Forschung


English Version | Leitseite des Instituts


Die Forschungsschwerpunkte des Instituts liegen im Bereich der Diskreten Mathematik und ihrer Anwendungen, insbesondere zu nennen sind Kombinatorische Optimierung und Chip-Design.

Die Kombinatorische Optimierung hat in den letzten Jahrzehnten wegen ihrer immensen Anwendungsrelevanz zunehmend an Bedeutung gewonnen. Am Forschungsinstitut für Diskrete Mathematik spielt sie schon immer eine wesentliche Rolle. Ausdruck dessen sind zahlreiche wegweisende Arbeiten der hiesigen Wissenschaftler und Gäste zu den unterschiedlichsten Fragestellungen der Kombinatorischen Optimierung. Der Artikel [1] gibt eine kurze Einführung. Einen umfassenden Überblick gibt das hier entstandene Standardwerk "Combinatorial Optimization" [2], von dem bereits fünf englische Auflagen erschienen sind; außerdem gibt es Übersetzungen nach Japanisch, Deutsch, Französisch, Italienisch, Russisch und Chinesisch. Der Tagungsband [3] des letzten Bonn Workshops zeigt neuere Forschungstrends. Im Juni 2014 organisierten wir IPCO, die führende Konferenz dieses Gebiets. Im Herbst 2015 gab es ein HIM-Trimesterprogramm über Kombinatorische Optimierung in Bonn. Ein Teil unserer aktuellen Forschungsaktivitäten konzentriert sich auf das Rundreiseproblem [4], und wir haben ein neue Kooperation begonnen, um Zustelldienste zu optimieren.

Das Chip-Design ist vielleicht das interessanteste und vielseitigste Anwendungsgebiet der Mathematik überhaupt. Ohne Methoden insbesondere der Diskreten Mathematik kann heute keiner der hochkomplexen Chips mehr entworfen werden. Viele dieser Methoden sind hier am Institut entwickelt worden. Unsere enge Kooperation mit der Industrie ermöglicht das Arbeiten an den aktuellsten Technologien und den komplexesten Chips. Unsere "BonnTools" [5], die unter anderem innovative Algorithmen für Placement, Routing, Timing-Optimierung und Layout auf Transistorebene beinhalten, werden weltweit eingesetzt. Der Artikel [6] gibt eine kurze Einführung in das Chip-Design. Einen umfassenden Überblick gibt [7].

Zu den genannten Hauptthemen kann als einführende Literatur empfohlen werden:
[1] J. Vygen: Combinatorial Optimization. Princeton Companion of Applied Mathematics, Princeton University Press 2015 [Download]
[2] B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. Springer, Berlin, Fifth Edition 2012. [Informationen]
[3] W.J. Cook, L. Lovász, J. Vygen: Research Trends in Combinatorial Optimization. Springer, Berlin 2009. [Informationen]
[4] J. Vygen: New approximation algorithms for the TSP. OPTIMA 90 (2012), 1-12. [Download]
[5] B. Korte, D. Rautenbach, J. Vygen: BonnTools: Mathematical innovation for layout and timing closure of systems on a chip. Proceedings of the IEEE 95 (2007), 555-572 [Download]
[6] S. Held, S. Hougardy, J. Vygen: Chip Design. Princeton Companion of Applied Mathematics, Princeton University Press 2015 [Download]
[7] S. Held, B. Korte, D. Rautenbach, J. Vygen: Combinatorial optimization in VLSI design. In: Combinatorial Optimization: Methods and Applications (V. Chvátal, ed.), IOS Press, Amsterdam 2011, pp. 33-96 [Download]
Die Quellen [2] und [7] enthalten zahlreiche weitere Literaturangaben. Außerdem gibt die Liste der am Institut entstandenen Technical Reports ein Bild über die Breite der Forschungsaktivitäten.

Das Forschungsinstitut für Diskrete Mathematik unterhält zahlreiche internationale Kooperationen und Drittmittelprojekte. Besonders erwähnenswert sind: