Profile
Profile

Prof. Dr. Jens Vygen

E-mail: vygen(at)or.uni-bonn.de
Phone: +49 228 73 8770
Fax: +49 228 73 8771
Homepage: http://gett.or.uni-bonn.de/~vygen/
Institute: Research Institute for Discrete Mathematics
Research Areas: Former Research Area K (Leader)
Research Area KL (Leader)
Former Research Area L
Date of birth: 30.May 1967
Mathscinet-Number: 364555

Academic Career

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

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 [4], the s-t-path TSP [5,6] and several related problems. To this end, we introduced several new techniques to this area, such as optimized ear-decompositons [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 min-max 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 vertex-disjoint spanning subgraphs are related. 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. This includes the price-collecting 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 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
Director

HIM Trimester on Combinatorial Optimization
Organizer, 2015

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

Contribution to Research Areas

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 (block-angular) min-max 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 well-known multi-commodity 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 graph-TSP [4], the s-t-path TSP [5,6], d-dimensional 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 next-generation computer chips, which are the most complex structures that mankind has ever designed.

Selected Publications

[1] Bernhard Korte, Jens Vygen
Combinatorial optimization
Theory and algorithms
of Algorithms and Combinatorics : xx+659
Publisher: Springer, Heidelberg
2012
ISBN: 978-3-642-24487-2
DOI: 10.1007/978-3-642-24488-9
[2] 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
[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 Computer-Aided Design
ICCAD '15 : 102--109
Publisher: IEEE Press, Piscataway, NJ, USA
2015
ISBN: 978-1-4673-8389-9
[4] András Sebő, 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
[5] Jens Vygen
Reassembling trees for the traveling salesman
SIAM J. Discrete Math. , 30: (2): 875--894
2016
DOI: 10.1137/15M1010531
[6] 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
[7] 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
[8] Stefan Hougardy, Jannik Silvanus, Jens Vygen
Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
Mathematical Programming Computation : 1--68
2016
DOI: 10.1007/s12532-016-0110-1
[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:1--32: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

Publication List

Editorships

• 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

Selected Invited Lectures

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

Supervised Theses

  • Master theses: 16
  • Diplom theses: 48
  • PhD theses: 23
Download Profile