

1992  Diploma, University of Bonn  1992  2003  Various Assistant Positions, University of Bonn  1995  2003  Stays at Budapest (Hungary), Institute for Mathematics and its Applications Minneapolis (MN, USA), IBM Research, and Yale (CT, USA)  1997  Dr. rer. nat., University of Bonn  2001  Habilitation, University of Bonn  Since 2003  Professor (C4/W3), Chair of Discrete Mathematics, University of Bonn  2011  2012  Visiting Professor, University of Grenoble, France 


My research is in combinatorial optimization [1] and its applications. Recently, we made significant progress in improving approximation ratios for the famous traveling salesman problem, yielding the best known ratios for graphTSP [4], the stpath TSP [5,6] and several related problems. To this end, we introduced several new techniques to this area, such as optimized eardecompositons [4], forest representations of hypergraphs [4], local parity correction [4], reassembling trees [5], and a global decomposition theorem [6]. Another classical combinatorial optimization problems which I worked on recently is the Steiner tree problem. We found the theoretically [7] and the practically [8] fastest algorithm in many cases. Steiner trees are also key objects in chip design, but here they must be packed in a huge graph subject to timing constraints and other aspects. We devised the fastest known algorithm (in theory and practice) for the very general minmax resource sharing problem (which includes, for instance, a better algorithm for multicommodity flows) [2] and applied it in a new way to optimize global routing with timing constraints [3], yielding the first such algorithm with a provable guarantee. This is a key element of BonnRoute [9], an algorithm that is part of the BonnTools and has been used for the design of thousands of complex chips. The constant need for new and very efficient algorithms to solve very hard practical problems inspires the development of combinatorial optimization. The interplay between fundamental theory, efficient algorithms, and industrial practice is extremely interesting.
The recently developed new techniques for the traveling salesman problem are definitely not yet fully exploited. In the future, we hope to improve further approximation ratios of the TSP and its variants, hopefully including Christofides’ 3/2 approximation ratio from 1976 and making progress on the famous 4/3 conjecture. Other classical problems such as finding small edge or vertexdisjoint spanning subgraphs are related. Also the stpath TSP is not yet fully understood, although great progress has been made. The only important case where the integrality ratio is known today is the graph stpath TSP, but even there it might be possible to improve the approximation ratio below this threshold. We also plan to extend the approximation algorithm to more general practical settings, including ones with several vehicles. Other fundamental problems in combinatorial optimization, in particular network design problems, are also challenging and not fully understood yet. This includes the pricecollecting Steiner forest problem and a generalization of the VPN problem. On the application side, after having integrated timing optimization and routing for the first time, we plan to extend our model to include buffering and hopefully also placement, in order to obtain a general model for chip design that allows global optimization in a single step. In the theoretical foundation of timing optimization, but also in project scheduling, the discrete timecost tradeoff problem plays a key role. We would like to understand why essentially no approximation algorithm is known for this problem, and hopefully find one.


Largescale cooperation on “Combinatorial optimization in chip design” with IBM
Management, jointly with Bernhard Korte
Longterm research project “Discrete Mathematics and Applications” of the North RhineWestphalian Academy of Sciences, Humanities and the Arts, Düsseldorf
Director, 2004  2012
DFG Cluster of Excellence “Hausdorff Center for Mathematics”
Principal Investigator
Research Area KL
Leader


Research Area KL Most of my research is devoted to combinatorial optimization [1] in a quite broad sense, and to efficient algorithms for chip design. The interplay between theory and practice is particularly fruitful.
With Müller and Radke we designed and analyzed combinatorial fully polynomial approximation schemes for the (blockangular) minmax resource sharing problem [2]. Our algorithm is at the same time much faster and significantly more general than all previous ones. It is even faster in the linear special case, which includes the wellknown multicommodity flow problem. Our implementation solves huge instances almost optimally. Recently, we managed to incorporate timing constraints [3].
With Peyer and Rautenbach, we found a generalization of Dijkstra's shortest path algorithm that exploits the graph structure and is much faster on many instances from practice].
Another research topic of mine is approximation algorithms. For example, I improved the best known approximation ratio for various problems, including the graphTSP [4], the stpath TSP [5,6], ddimensional arrangement, universal facility location, and sink clustering. Our new exact algorithms for the classical Steiner tree problem in graphs [7,8] are faster than all previous ones in many cases.
We also continued our work on the mathematics of chip design. We advanced the state of the art in placement, repeater tree design, and routing [3,9].
Our BonnTools are being used in industry for the design of nextgeneration computer chips, which are the most complex structures that mankind has ever designed. 


[ 1] Bernhard Korte, Jens Vygen
Combinatorial optimization Theory and algorithms of Algorithms and Combinatorics : xx+659 Publisher: Springer, Heidelberg 2012 ISBN: 9783642244872 DOI: 10.1007/9783642244889[ 2] Dirk Müller, Klaus Radke, Jens Vygen
Faster minmax resource sharing in theory and practice Math. Program. Comput. , 3: (1): 135 2011 DOI: 10.1007/s125320110023y[ 3] Stephan Held, Dirk Müller, Daniel Rotter, Vera Traub, Jens Vygen
Global Routing with Inherent Static Timing Constraints Proceedings of the IEEE/ACM International Conference on ComputerAided Design ICCAD '15 : 102109 Publisher: IEEE Press, Piscataway, NJ, USA 2015 ISBN: 9781467383899[ 4] András Sebő, Jens Vygen
Shorter tours by nicer ears: 7/5approximation for the graphTSP, 3/2 for the path version, and 4/3 for twoedgeconnected subgraphs Combinatorica , 34: (5): 597629 2014 DOI: 10.1007/s0049301429603[ 5] Jens Vygen
Reassembling trees for the traveling salesman SIAM J. Discrete Math. , 30: (2): 875894 2016 DOI: 10.1137/15M1010531[ 6] Corinna Gottschalk, Jens Vygen
Better sttours by Gao trees Integer programming and combinatorial optimization of Lecture Notes in Comput. Sci. : 126137 Publisher: Springer, [Cham] 2016 DOI: 10.1007/9783319334615_11[ 7] Jens Vygen
Faster algorithm for optimum Steiner trees Inform. Process. Lett. , 111: (2122): 10751079 2011 DOI: 10.1016/j.ipl.2011.08.005[ 8] Stefan Hougardy, Jannik Silvanus, Jens Vygen
Dijkstra meets Steiner: a fast exact goaloriented Steiner tree algorithm Mathematical Programming Computation : 168 2016 DOI: 10.1007/s1253201601101[9] Michael Gester, Dirk Müller, Tim Nieberg, Christian Panten, Christian Schulte, Jens Vygen
BonnRoute: Algorithms and data structures for fast and good VLSI routing ACM Trans. Des. Autom. Electron. Syst. , 18: (2): 32:132:24 Publisher: ACM, New York, NY, USA 2013 DOI: 10.1145/2442087.2442103 [ 10] Jens Maßberg, Jens Vygen
Approximation algorithms for a facility location problem with service capacities ACM Trans. Algorithms , 4: (4): Art. 50, 15 2008 DOI: 10.1145/1383369.1383381



• Operations Research Letters (2002  2015)
• Discrete Optimization (2003  2017)
• Mathematical Programming (Series A) (2004  2016)
• ACM Transactions on Design Automation of Electronic Systems (2013  2016)
• Mathematics of Operations Research (area editor for discrete optimization, since 2015)
• INFORMS Journal on Computing (since 2016)
Program committee member of IPCO (2002, 2011, 2014), ICCAD (2002, 2005), ESA (2003), DATE (2004, 2005, 2008), ISPD (2006), DAC (2009), ISAAC (2011), and other international conferences


2009  23rd European Conference on Operations Research, keynote lecture, Bonn  2012  Third Cargese Workshop on Combinatorial Optimization, distinguished lecture series, France  2016  DIAMOND symposium, Veenendaal, Netherlands  2016  FIM workshop on combinatorial optimization, Zürich, Switzerland 


 Master theses: 16
 Diplom theses: 48
 PhD theses: 23


Download Profile 