Research Institute for Discrete Mathematics

Research


Deutsche Version | Home page of the institute


The institute's central research activities focus on the area of Discrete Mathematics and its applications, particularly on combinatorial optimization and chip design.

Combinatorial Optimization has become more and more important during the last decades, due to its immense significance for applications. At the Research Institute for Discrete Mathematics, it has always played a major role. This becomes obvious in the many pioneering works by the institute's scientists and guests, dealing with the most diverse problems in the field of combinatorial optimization. The article [1] gives a brief introduction. Our standard work "Combinatorial Optimization" [2] provides a more comprehensive overview. This book has already five English editions and translations into Japanese, German, French, Italian, Russian, and Chinese. The proceedings [3] of the last Bonn workshop presents recent research trends. In June 2014, we hosted IPCO, the leading conference of this field. In fall 2015, there was a HIM trimester program on combinatorial optimization in Bonn. Some of our recent research focuses on the traveling salesman problem [4], and we started a new cooperation on optimizing delivery services.

Chip Design is probably the most interesting and varied range of application of mathematics in general. Modern highly complex chips cannot be designed without the use of methods of discrete mathematics. Many of these methods have been developed at this institute. Our close cooperation with industry enables us to work with the latest technologies and the most complex chips. Our "BonnTools" [5], which comprise innovative algorithms for placement, routing, timing optimization, transistor-level layout and more, are used all over the world. The article [6] gives a brief introduction to chip design. A good survey is given by [7].

Recommended publications as introduction to the main fields of interest:
[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. [Information]
[3] W.J. Cook, L. Lovász, J. Vygen: Research Trends in Combinatorial Optimization. Springer, Berlin 2009. [Information]
[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]
The sources [2] and [7] contain numerous references to further reading. Besides this, the list of technical reports that have been produced at the institute gives a good impression of the wide range of research activities.

The Research Institute for Discrete Mathematics maintains many international cooperations and third-party projects, amongst which the following are particularly noteworthy: