Prof. Dr. Jens Vygen

E-mail: vygen(at)
Phone: +49 228 73 8770
Fax: +49 228 73 8771
Institute: Research Institute for Discrete Mathematics
Research Area: Research Area C3

Academic Career


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)


Dr. rer. nat., University of Bonn


Habilitation, University of Bonn

Since 2003

Professor (C4/W3), Chair of Discrete Mathematics, University of Bonn

2011 - 2012

Visiting Professor, University of Grenoble, France

2019 - 2020

Visiting Professor, ENS Paris and ETH Zurich

Research Profile

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 graph-TSP [2], the s-t-path TSP [3,4,5] and several related problems, including finding a smallest 2-edge- or 2-vertex-connected subgraph. To this end, we introduced several new techniques to this area, such as optimized ear-decompositons [2], forest representations of hypergraphs [2], local parity correction [2], reassembling trees [3], and a global decomposition theorem [4], and recursive dynamic programming [5]. Another classical combinatorial optimization problems which I worked on recently is the Steiner tree problem. We found the theoretically [6] and the practically [7] 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 min-max resource sharing problem (which includes, for instance, a better algorithm for multicommodity flows) [8] and applied it in a new way to optimize global routing with timing constraints [9], yielding the first such algorithm with a provable guarantee. This is a key element of BonnRoute [10], 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. Simplifying and improving the recent constant-factor approximation for the asymmetric TSP is another goal. Also the s-t-path 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 s-t-path 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. 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 time-cost 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.

Research Projects and Activities

Large-scale cooperation on “Combinatorial optimization in chip design” with IBM
Management, jointly with Bernhard Korte

Cooperation “Combinatorial Optimization for Applications in Pickup and Delivery Services” with Deutsche Post/DHL

HIM Trimester on Combinatorial Optimization
Organizer, 2015

Oberwolfach Workshop on Combinatorial Optimization
Organizer, 2011

Long-term research project “Discrete Mathematics and Applications” of the North Rhine-Westphalian 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

Selected Publications

[2] András Seb\~{o}, Jens Vygen
Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
Combinatorica , 34: (5): 597--629
DOI: 10.1007/s00493-014-2960-3
[3] Jens Vygen
Reassembling trees for the traveling salesman
SIAM J. Discrete Math. , 30: (2): 875--894
DOI: 10.1137/15M1010531
[4] Corinna Gottschalk, Jens Vygen
Better s-t-tours by Gao trees
Integer programming and combinatorial optimization
of Lecture Notes in Comput. Sci. : 126--137
Publisher: Springer, [Cham]
DOI: 10.1007/978-3-319-33461-5_11
[5] Vera Traub, Jens Vygen
Approaching 3/2 for the s-t-path TSP.
Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
(Best Paper Award)
DOI: 10.1137/1.9781611975031.121
[6] Jens Vygen
Faster algorithm for optimum Steiner trees
Inform. Process. Lett. , 111: (21-22): 1075--1079
DOI: 10.1016/j.ipl.2011.08.005
[7] Stefan Hougardy, Jannik Silvanus, Jens Vygen
Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
Math. Program. Comput. , 9: (2): 135--202
DOI: 10.1007/s12532-016-0110-1
[8] Dirk Müller, Klaus Radke, Jens Vygen
Faster min-max resource sharing in theory and practice
Math. Program. Comput. , 3: (1): 1--35
DOI: 10.1007/s12532-011-0023-y
[9] Stephan Held, Dirk Müller, Daniel Rotter, Rudolf Scheifele, Vera Traub, Jens Vygen
Global Routing with Timing Constraints
IEEE Trans. on CAD of Integrated Circuits and Systems , 37: : 406--419
[10] 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:1--32:24
Publisher: ACM, New York, NY, USA
DOI: 10.1145/2442087.2442103

Publication List

MathSciNet Publication List (external link)

ArXiv Preprint List (external link)


• 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 (2016 - 2019)
• Mathematical Programming A: (Co-Editor, since 2019)

Program committee member of IPCO (2002, 2011, 2014), ICCAD (2002, 2005), ESA (2003), DATE (2004, 2005, 2008), ISPD (2006), DAC (2009), ISAAC (2011), ICALP (2020) and other international conferences.



Faculty Teaching Award


Best Paper Award of the ACM-SIAM Symposium on Discrete Algorithms


Best Paper Award of the Conference on Integer Programming and Combinatorial Optimization

Selected Invited Lectures


23rd European Conference on Operations Research, keynote lecture, Bonn


Third Cargese Workshop on Combinatorial Optimization, distinguished lecture series, France


DIAMOND symposium, Veenendaal, Netherlands


FIM workshop on combinatorial optimization, Zürich, Switzerland


Workshop on the traveling salesman problem, Banff, Canada


Workshop on combinatorial optimization, Oberwolfach


International Computer Science Symposium in Russia, Sochi, Russia

Supervised Theses

  • Master theses: 20
  • Diplom theses: 48
  • PhD theses: 25
Download Profile