|
|
|
| 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 | | 2019 - 2020 | Visiting Professor, ENS Paris and ETH Zurich |
|
|
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.
|
|
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
Director
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
Leader
|
|
[ 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
2014
DOI: 10.1007/s00493-014-2960-3[ 3] Jens Vygen
Reassembling trees for the traveling salesman
SIAM J. Discrete Math. , 30: (2): 875--894
2016
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]
2016
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)
2018
DOI: 10.1137/1.9781611975031.121[ 6] Jens Vygen
Faster algorithm for optimum Steiner trees
Inform. Process. Lett. , 111: (21-22): 1075--1079
2011
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
2017
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
2011
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
2018[ 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
2013
DOI: 10.1145/2442087.2442103 |
|
|
|
|
|
|
|
• 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.
|
|
| 2016 | Faculty Teaching Award | | 2018 | Best Paper Award of the ACM-SIAM Symposium on Discrete Algorithms | | 2021 | Best Paper Award of the Conference on Integer Programming and Combinatorial Optimization |
|
|
| 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 | | 2018 | Workshop on the traveling salesman problem, Banff, Canada | | 2018 | Workshop on combinatorial optimization, Oberwolfach | | 2021 | International Computer Science Symposium in Russia, Sochi, Russia |
|
|
- Master theses: 20
- Diplom theses: 48
- PhD theses: 25
|
|
Download Profile  |
