

2008  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 


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 twolevel 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 carrybit calculation from cubic to nearlinear [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 timingconstrained 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 carrybit circuits computed by the algorithm from [11] are fastest possible when restricting to so called prefix gates, which are predominantly 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 NPhard 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 subpartitions.


“Combinatorial Optimization and Chip Design”,
longterm cooperation funded by IBM Corporation, since 2010


Former Research Area K Most combinatorial optimization problems are hard to solve. Sometimes, they even cannot be approximated with a nontrivial approximation guarantee unless P = NP. However, often exact solutions are still of great importance in practical applications. For graph coloring and the maximumweight 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]. 


[ 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. : 261273 Publisher: Springer, Heidelberg 2011 DOI: 10.1007/9783642208072_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 ComputerAided Design 2003[ 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 2006[ 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 2009[ 5] C. Bartoschek, S. Held, J. Maßberg, D. Rautenbach, J. Vygen
The repeater tree construction problem Inform. Process. Lett. , 110: (24): 10791083 2010 DOI: 10.1016/j.ipl.2010.08.016[ 6] S. Held
Gate sizing for large cellbased designs Proceedings Design Automation & Test in Europe 2009 Best Paper Award 2009[ 7] Stephan Held, Daniel Rotter
Shallowlight Steiner arborescences with vertex delays Integer programming and combinatorial optimization of Lecture Notes in Comput. Sci. : 229241 Publisher: Springer, Heidelberg 2013 DOI: 10.1007/9783642366949_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 : 3744 2014[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 ComputerAided Design : 102109 2015 [10] Stephan Held, Nicolas Kämmerling
Twolevel rectilinear Steiner trees Comput. Geom. , 61: : 4859 2017 DOI: 10.1016/j.comgeo.2016.11.002 [ 11] Stephan Held, Sophie Spirkl
Fast prefix adders for nonuniform input arrival times Algorithmica , 77: (1): 287308 2017 DOI: 10.1007/s004530150067x[ 12] S. Held, U. Schorr
Postrouting latch optimization for timing closure Proc. 51st Design Automation Conference, ACM , 7: (6): 17 2014[ 13] A. Bock, S. Held, N. Kämmerling, U. Schorr
Local search algorithms for timingdriven placement under arbitrary delay models Proc. 52th Design Automation Conference, ACM , 29: (6): 129 2015[ 14] S. Held, J. Hu
Gate sizing Electronic Design Automation for Integrated Circuits Handbook (2nd edition) Publisher: CRC press 2016[ 15] Stephan Held, William Cook, Edward C. Sewell
Maximumweight stable sets and safe lower bounds for graph coloring Math. Program. Comput. , 4: (4): 363381 2012



• IEEE Transactions on ComputerAided 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 ComputerAided Design (since 2016)


2006  NATO summer school on combinatorial optimization, Montreal, QC, Canada  2009  Spring School on Mathematics of Chip Design, Hangzhou, China 


 Master theses: 7, currently 3
 Diplom theses: 2
 PhD theses: 2, currently 2


Download Profile 