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. We are frequently hosting various international scientific meetings.

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" [3], which comprise innovative algorithms for placement, routing, timing optimization, transistor-level layout and more, are used all over the world. The article [4] gives a brief introduction to chip design. A more comprehensive survey is given by [5].

Vehicle Routing is another application area that we are pursuing. Some years ago, based on our recent research on the traveling salesman problem [6], we started a new cooperation on optimizing delivery services. Besides the theoretical study of approximation algorithms for traveling salesman and vehicle routing problems (see, e.g., [7]), we are developing an algorithm for real-world vehicle routing problems, taking time-dependent travel times, heterogenous fleets, time windows, and many other constraints into account (see [8]).

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, Sixth Edition 2018. [Information]

[3] 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]
[4] S. Held, S. Hougardy, J. Vygen: Chip Design. Princeton Companion of Applied Mathematics, Princeton University Press 2015 [Download]

[5] 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]

[6] V. Traub, J. Vygen: Approximation algorithms for traveling salesman problems. Cambridge University Press 2025 (in press)

[7] J. Blauth, V. Traub, J. Vygen: Improving the approximation ratio for capacitated vehicle routing. Mathematical Programming 197 (2023), 451-497 [arXiv]

[8] J. Blauth, S. Held, D. Müller, N. Schlomberg, V. Traub, T. Tröbst, J. Vygen: Vehicle routing with time-dependent travel times: theory, practice, and benchmarks. Discrete Optimization 53 (2024), 100848 [arXiv]

The sources [2], [5], and [6] 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:

an industrial cooperation with IBM on "Combinatorial Optimization and Chip Design", persisting for more than 30 years.
a new cooperation with Deutsche Post/DHL and her start-up company Greenplan on "Combinatorial Optimization for Applications in Pickup and Delivery Services".
the participation in the Hausdorff Center for Mathematics (Cluster of Excellence), leading the research areas "Optimization in Large and Complex Networks" (2006-2012), "Algorithms, combinatorics, and complexity" (2012-2018) and "Combinatorial optimization, complexity, and chip design" (2019-2025).

[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, Sixth Edition 2018. [Information]
[3]	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]
[4]	S. Held, S. Hougardy, J. Vygen: Chip Design. Princeton Companion of Applied Mathematics, Princeton University Press 2015 [Download]
[5]	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]
[6]	V. Traub, J. Vygen: Approximation algorithms for traveling salesman problems. Cambridge University Press 2025 (in press)
[7]	J. Blauth, V. Traub, J. Vygen: Improving the approximation ratio for capacitated vehicle routing. Mathematical Programming 197 (2023), 451-497 [arXiv]
[8]	J. Blauth, S. Held, D. Müller, N. Schlomberg, V. Traub, T. Tröbst, J. Vygen: Vehicle routing with time-dependent travel times: theory, practice, and benchmarks. Discrete Optimization 53 (2024), 100848 [arXiv]