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 Area: Research Area C3

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 [1,2,3], potentially with obstacles [4], and subsequent repeater insertion [5]. 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 [6].
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 [7]. 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 [8]. Other important aspects of signal speed optimization are the gate placement and sizing [9,10,11,12].
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 [6] 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 [8] 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

Selected Publications

[1] 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
[2] 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
[3] 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
[7] Stephan Held, Nicolas Kämmerling
Two-level rectilinear Steiner trees
Comput. Geom. , 61: : 48--59
DOI: 10.1016/j.comgeo.2016.11.002
[8] 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
[13] S. Held, S.~T. Spirkl
Binary Adder Circuits of Asymptotically MinimumDepth, Linear Size, and Fan-Out Two
arxiv: 1503.08659v2
ACM Transactions on Algorithms, to appear
[14] Stephan Held, Dirk Muller, Daniel andScheifele, Rudolf Rotter, Vera Traub, Jens Vygen
Global Routing with Timing Constraints
IEEE Transactions on Computer-Aided Design ofIntegrated Circuits and Systems
Publisher: IEEE
[15] Stephan Held, Sophie Spirkl
Fast Prefix Adders for Non-uniform Input Arrival Times
77: (1): 287--308
Publisher: Springer US
[16] Stephan Held, Daniel Rotter
Shallow-Light Steiner Arborescences with VertexDelays.
[17] Stephan Held, William Cook, Edward C Sewell
Maximum-weight stable sets and safe lower bounds forgraph coloring
Mathematical Programming Computation : 1--19
Publisher: Springer Berlin/Heidelberg
[18] Christoph Bartoschek, Stephan andMaÃ?berg, Jens Held, Dieter Rautenbach, Jens Vygen
The repeater tree construction problem
Information Processing Letters
, 110: (24): 1079--1083
Publisher: Elsevier
[19] Stephan Held
Gate sizing for large cell-based designs
Proceedings of the Conference on Design, Automationand Test in Europe
Best paper award at DATE'09
[20] Stephan Held, Bernhard Korte, Jens Maβberg, Matthias Ringe, Jens Vygen
Clock scheduling and clocktree construction for highperformance ASICs
Proceedings of the 2003 IEEE/ACM internationalconference on Computer-aided design

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 (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: 13, currently 3
  • Diplom theses: 2
  • PhD theses: 3, currently 2
Download Profile