Prof. Dr. Stephan Held

E-mail: held(at)
Phone: +49 228 73 8740
Fax: +49 228 73 8771
Room: 303
Institute: Research Institute for Discrete Mathematics
Bonn International Graduate School - BIGS
Research Areas: Research Area KL
Former Research Area K
Date of birth: 04.May 1976

Academic Career


Dr. rer. nat., University of Bonn

2009 - 2010

Postdoc, Georgia Institute of Technology, Atlanta, GA, USA

2010 - 2013

Junior Professor (W1), University of Bonn

2013 - 2016

Professor (W2), tenure track, University of Bonn

Since 2016

Professor (W2), University of Bonn

Research Profile

My current research focus is on combinatorial optimization and its application in chip design. Here, one of the major problems is the Steiner tree problem, which occurs in various variants. The major problem is to find Steiner trees for fast but economic signal distribution [3,5,7], potentially with obstacles [8], and subsequent repeater insertion [4]. Steiner trees on a chip cannot be designed independently but are mutually dependent in their space consumption and signal speeds. Here we showed how to to incorporate all constraints into a common resource sharing model and solve its continuous relaxation efficiently [9].
Steiner trees occur also in the realization of parity functions and similar commutative functions. Here there are also side terminals besides the major terminals and the problems becomes a two-level Steiner tree problem [10]. However, most logic functions are more complex than parity calculations. One of the most important ones is binary addition, for which we improved the running time for optimizing the depth of carry-bit calculation from cubic to near-linear [11]. Other important aspects of signal speed optimization are the gate placement and sizing [6,12,13,14].
A major challenge in chip design is the huge number of design variables and constraints. While some specific subproblems, such as placement, buffering, gate sizing, and routing can be solved more or less well in practice, approaches tackling several of these steps are mostly build on heuristics. We plan to continue the approach for timing-constrained global routing in [9] to integrate most design variables into a single global mathematical problem formulation, aiming provably good computer chips.
We will continue to find better structures for logic functions. The carry-bit circuits computed by the algorithm from [11] are fastest possible when restricting to so called prefix gates, which are pre-dominantly used in industry. When abandoning this paradigm, faster adders are possible, but were hardly investigated in the last 40 years. We want to characterize the general best tradeoffs between depth, size, and interconnect complexity for adders and other functions on modern computer chips. A new focus is related to the traveling salesman problem (TSP). The major application of the TSP in practice is the vehicle routing problem, where cities have to be partitioned to multiple salesmen, which visit their bounded number of cities in a tour. The total length of all tours is to be minimized. For this problem it is not even clear whether the separation of the so called subtour inequalities is NP-hard or solvable in polynomial time. A polynomial time algorithm would have immediate positive consequences to many practical applications in logistics. Another interesting question in this respect is the best topology of such a tour network. We want to study the benefit of further sub-partitions.

Research Projects and Activities

“Combinatorial Optimization and Chip Design”,
long-term cooperation funded by IBM Corporation, since 2010

Contribution to Research Areas

Former Research Area K
Most combinatorial optimization problems are hard to solve. Sometimes, they even cannot be approximated with a non-trivial approximation guarantee unless P = NP. However, often exact solutions are still of great importance in practical applications. For graph coloring and the maximum-weight stable set problem, the size of practically solvable problems could be increased significantly with new elaborate bounding methods and numerically safe rounding of floating point calculations [1].

A large number of mathematical optimization problems arise in chip design [2]. Repeater insertion [3,4,5] and gate sizing [6] are the two central problems in the timing optimization of a computer chip. For repeater insertion, a new network design problem, the “Repeater Tree Problem” [3,5], is solved to find an initial topology and geometry of the repeater tree. This is used as a guidance for the final topology determination and repeater insertion [4].

Selected Publications

[1] Stephan Held, William Cook, Edward C. Sewell
Safe lower bounds for graph coloring
Integer programming and combinatorial optimization
of Lecture Notes in Comput. Sci. : 261--273
Publisher: Springer, Heidelberg
DOI: 10.1007/978-3-642-20807-2_21
[2] S. Held, B. Korte, J. Maßberg, M. Ringe, J. Vygen
Clock scheduling and clocktree construction for high performance ASICs
Proceedings of the IEEE/ACM International Conference on Computer-Aided Design
[3] C. Bartoschek, S. Held, D. Rautenbach, J. Vygen
Efficient Generation of Short and Fast Repeater Tree Topologies
Proceedings of the International Symposium on Physical Design
[4] C. Bartoschek, S. Held, D. Rautenbach, J. Vygen
Fast buffering for optimizing worst slack and resource consumption in repeater rrees
Proceedings International Symposium on Physical Design
[5] C. Bartoschek, S. Held, J. Maßberg, D. Rautenbach, J. Vygen
The repeater tree construction problem
Inform. Process. Lett. , 110: (24): 1079--1083
DOI: 10.1016/j.ipl.2010.08.016
[6] S. Held
Gate sizing for large cell-based designs
Proceedings Design Automation & Test in Europe 2009
Best Paper Award
[7] Stephan Held, Daniel Rotter
Shallow-light Steiner arborescences with vertex delays
Integer programming and combinatorial optimization
of Lecture Notes in Comput. Sci. : 229--241
Publisher: Springer, Heidelberg
DOI: 10.1007/978-3-642-36694-9_20
[8] S. Held, S.T. Spirkl
A fast algorithm for rectilinear Steiner trees with length restrictions on obstacles
Proceedings of the International Symposium on Physical Design, ACM : 37--44
[9] S. Held, D. Müller, D. Rotter, V. Traub, J. Vygen
Global routing with inherent static timing constraints
Proceedings of the IEEE/ACM International Conference on Computer-Aided Design : 102--109
[10] Stephan Held, Nicolas Kämmerling
Two-level rectilinear Steiner trees
Comput. Geom.
61: : 48--59
DOI: 10.1016/j.comgeo.2016.11.002
[11] Stephan Held, Sophie Spirkl
Fast prefix adders for non-uniform input arrival times
Algorithmica , 77: (1): 287--308
DOI: 10.1007/s00453-015-0067-x
[12] S. Held, U. Schorr
Post-routing latch optimization for timing closure
Proc. 51st Design Automation Conference, ACM , 7: (6): 1--7
[13] A. Bock, S. Held, N. Kämmerling, U. Schorr
Local search algorithms for timing-driven placement under arbitrary delay models
Proc. 52th Design Automation Conference, ACM , 29: (6): 1--29
[14] S. Held, J. Hu
Gate sizing
Electronic Design Automation for Integrated Circuits Handbook (2nd edition)
Publisher: CRC press
[15] Stephan Held, William Cook, Edward C. Sewell
Maximum-weight stable sets and safe lower bounds for graph coloring
Math. Program. Comput. , 4: (4): 363--381

Publication List


• IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (since 2016)

Member in technical program committees of conferences with published proceedings:
• International Symposium on Physical Design (2014 - 2016)
• International Conference on Computer-Aided Design (since 2016)

Selected Invited Lectures


NATO summer school on combinatorial optimization, Montreal, QC, Canada


Spring School on Mathematics of Chip Design, Hangzhou, China

Supervised Theses

  • Master theses: 7, currently 3
  • Diplom theses: 2
  • PhD theses: 2, currently 2
Download Profile