Professor Dr.

Stephan Held

Combinatorial optimization
from theory to applications.

Chip design · Graph coloring · Vehicle routing

Contact

Research Institute for Discrete Mathematics
Lennéstr. 2 · 53113 Bonn · Germany
Office: Room 303
held@dm.uni-bonn.de
+49 228 738740

Research interests

VLSI-Design:
- I work on many topics mostly in collaboration with IBM.
- Clock Scheduling and Construction (Instances for the minimum mean cycle problem)
- Gate Sizing
- Repeater Trees
- Threshold Voltage Optimization. Large minimum-cost flow instances arising in the linear time-cost tradeoff relaxation of threshold voltage optimization and placement.
- Logic Resynthesis
- Timing Driven Placement & Routing

Vehicle Routing:
- Just Passing Through the TSP code with which William Cook, Keld Helsgaun, and I could win the 2021 Last Mile Routing Challenge organized by Amazon and the MIT Center for Transportation and Logistics (press release of the University of Bonn). William Cook created a nice web page describing the contest and our approach.
- Combinatorial optimization for practical pickup and delivery services in cooperation with Greenplan.
- In 2022, we created real-world instances with time-dependent travel times using OpenStreetMap data and Uber speed profiles. More details can be found in our paper Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks. See also the archived version of the new benchmarks.
- Uniform CVRP instances from VLSI design. These instances arise in chip design, when scan chains are grouped and ordered to minimize the total netlength of the chains.
Graph Coloring:
exactcolors one of the fastest open source codes for the maximum-weight stable set and the graph coloring problem. ZykovColor leverages an incremental SAT solver.

I serve as an associate editor of Discrete Optimization.

Publications

T. Brand, D. Faber, S. Held, and P. Mutzel: A Customized SAT-based Solver for Graph Coloring. Proc. ALENEX 2026, 142--155, arXiv:2504.04821, 2025. See also our corresponding source code .
S. Held and E. Perner: Cost-Distance Steiner Trees for Timing-Constrained Global Routing. Proc. DAC 2025. arxiv:2503.04419, 2025.
T. Brand and S. Held: Fractional Chromatic Numbers from Exact Decision Diagrams. arXiv:2411.03003, 2024. See also our corresponding code and data archive .
J. Blauth, S. Held, D. Müller, N. Schlomberg, V. Traub, T. Tröbst, and J. Vygen: Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks. Discrete Optimization, Volume 53,100848, 2024, arXiv.2205.00889 (preprint), new benchmarks for VRP with time-dependent travel times.
W. Cook, S. Held. K. Helsgaun: Local Search with Learned Constraints for Last Mile Routing, Transportation Science 58(1), 12--26, 2024, preprint: arXiv:2112.15192, describing our approach for winning the 2021 Last Mile Routing Challenge by Amazon and MIT with significant post-contest improvements.
A short version can be found in the Technical Proceedings of the Amazon Last Mile Routing Research Challenge, editors M. Winkenbach, S. Parks and J. Noszek, article XXI, 2021
J. Foos, S. Held and Y.K.D. Spitzley: Tighter Approximation of the Uniform Cost-Distance Steiner Tree Problem, APPROX/RANDOM 2023, LIPIcs 275, 19:1--19:16, 2023, prerprint arXiv:2305.03381.
S. Daboul, S. Held, B. Natura, D. Rotter: Global Interconnect Optimization, ACM Transactions on Design Automation of Electronic Systems 28 (5), Article No.: 72, 24 pages, 2023, TR with minor fixes in blue. preliminary short version: Proc. ICCAD 2019, pp. 1--8. doi: 10.1109/ICCAD45719.2019.8942155
S. Held and Y.K.D. Spitzley: Further Improvements on Approximating the Uniform Cost-Distance Steiner Tree Problem, Technical Report No. 221263, Research Institute for Discrete Mathematics, University of Bonn, 2022, arXiv:2211.03830.
G. Posser, E.F.Y. Young, S. Held, Y.-L. Li, D.Z. Pan: Challenges and Approaches in VLSI Routing Proc. ISPD, 2022, (preprint),
S. Daboul, S. Held, and J. Vygen: Approximating the discrete time-cost tradeoff problem with bounded depth, Mathematical Programming, 2022, (preprint: arxiv 2011.02446), Short version in Proc. IPCO 2021, pp. 30--42.
A. Khazraei and S. Held: An Improved Approximation Algorithm for the Uniform Cost-Distance Steiner Tree Problem, Proc. WAOA 2020, LNCS 12806, pp. 189--203, 2021. (preprint).
S. Held, J. Könemann, J. Vygen: Vehicle Routing with Subtours, Discrete Optimization 33, 87--100, 2019, (preprint, arXiv:1801.04991).
S. Daboul, S. Held, J. Vygen, and S. Wittke: An approximation algorithm for threshold voltage optimization, ACM Transactions on Design Automation of Electronic Systems 23 (6), Article No. 68, 2018. (preprint).
S. Held and B. Rockel: Exact Algorithms for Delay-Bounded Steiner Arborescences, 2018, DAC 2018, Article no. 44, (best paper award).
S. Daboul, N. Hähnle, S. Held, and U. Schorr: Provably Fast and Near-Optimum Gate Sizing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 37(12), 3163--3176 , 2018, (preprint).
S. Held and S.T.Spirkl: Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out Two. ACM Transactions on Algorithms 14(1), Articel No 4, , 2018, ( preprint ).
S. Held, D. Müller, D. Rotter, R. Scheifele, V. Traub, and J. Vygen: Global Routing with Timing Constraints, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 37(2), 2018, 406--419. (10.1109/TCAD.2017.2697964), (preprint).
S. Held and N. Kämmerling: Two-Level Rectilinear Steiner Trees, Computational Geometry 61, 2017, 48--59 (link, preprint , short version at EUROCG 2015).
S. Held and S.T.Spirkl: Fast Prefix Adders for Non-Uniform Input Arrival Times, Algorithmica 77 (1), 2017, 287--308 (link, preprint).
S. Held and J. Hu: Gate Sizing, in Electronic Design Automation for IC Implementation, Circuit Design, and Process Technology. Edited by Luciano Lavagno, Igor L. Markov, Grant Martin, and Louis K. Scheffer, CRC Press, 2016, 245--260 (Chapter 10).
S. Held, D. Müller, Daniel Rotter, Vera Traub and J. Vygen: Global Routing with Inherent Static Timing Constraints. Proc. ICCAD 2015, 102--109.
S. Held, S. Hougardy, and J. Vygen: Chip Design. in: The Princeton Companion to Applied Mathematics, (N.J.Higham, ed.), Princeton University Press 2015, 804--807.
A. Bock, S. Held, N. Kämmerling, and U. Schorr: Local Search Algorithms for Timing-Driven Placement under Arbitrary Delay Models. Proc. 52th DAC, 2015, (preprint).
S. Held and U. Schorr: Post-Routing Latch Optimization for Timing Closure. Proc. 51st DAC, 2014.
S. Held and S. T. Spirkl: A Fast Algorithm for Rectilinear Steiner Trees with Length Restrictions on Obstacles. Proc. ISPD 2014, pp. 37--44.
S. Held and D. Rotter: Shallow Light Steiner Arborescences with Vertex Delays. Proc. IPCO 2013, pp. 229--241.
S. Held, E. C. Sewell, W. Cook: Maximum-Weight Stable Sets and Safe Lower Bounds for Graph Coloring, Mathematical Programming Computation: Volume 4, Issue 4 (2012), 363--381, preprint
S. Held, B. Korte, D. Rautenbach, J. Vygen: Combinatorial optimization in VLSI design . In: "Combinatorial Optimization: Methods and Applications" (V. Chvatal, ed.), IOS Press, Amsterdam, 2011, pp. 33--96.
S. Held, E. C. Sewell, W. Cook: Safe Lower Bounds for Graph Coloring. Proc. IPCO 2011, pp. 261--273 .
C. Bartoschek, S. Held, J. Maßberg, D. Rautenbach, J. Vygen: The repeater tree construction problem. Information Processing Letters 110 (2010), 1079-1083.
S. Held: Gate Sizing for Large Cell-Based Designs . Proc. DATE 2009, pp. 827--832. ( Best Paper Award )
C. Bartoschek, S. Held, D. Rautenbach, J. Vygen: Fast Buffering for Optimizing Worst Slack and Resource Consumption in Repeater Trees. Proc. ISPD 2009, pp. 43--50.
S. Held: Timing Closure in Chip Design. Dissertation, Universität Bonn, 2008.
C. Bartoschek, S. Held, D. Rautenbach, J. Vygen: Efficient algorithms for short and fast repeater trees. II. Buffering. Technical Report No. 07978, Research Institute for Discrete Mathematics, University of Bonn, 2007
C. Bartoschek, S. Held, D. Rautenbach, J. Vygen: Efficient algorithms for short and fast repeater trees. I. Topology generation. Technical Report No. 07977, Research Institute for Discrete Mathematics, University of Bonn, 2007
S. Held: Fast Gate Sizing and Timing Closure for Multi-Million Cell Designs. Technical Report No. 07969, Forschungsinstitut für Diskrete Mathematik, University of Bonn, 2007
C. Bartoschek, S. Held, D. Rautenbach, J. Vygen: Efficient Generation of Short and Fast Repeater Tree Topologies. Proc. ISPD 2006, pp. 120--127.
S. Held, B. Korte, J. Maßberg, M. Ringe, J. Vygen: Clock Scheduling and Clocktree Construction for High Performance ASICs. Proc. ICCAD 2003, pp. 232--239.

Conferences & schools

International Symposium on Physical Design, yearly: 2023-2027
Bonn Workshop on Compuational Combinatorial Optimization, October 17-21, 2022
Hausdorff Summer School on Compuational Combinatorial Optimization, September 12-16, 2022
The 17th Conference on Integer Programming and Combinatorial Optimization, June 23 - 25, 2014, Bonn - Germany
Spring School on Mathemtics of Chip Design, March 30 - April 8, 2009, Hangzhou, China.

Teaching

Students & applicants

Information for Prospective Students and Applicants:

I will not answer applications that are sent by e-mail

Internships: I am sorry, but I do not offer internships. Due to the large number of applications, I will not answer such requests.
Bachelor's and Master's Programs: Please do not send me applications directly, but rather contact the appropriate office for mathematics or computer science.
Doctoral Studies / PhD Program: You can send me your application directly at any time, but not by e-mail. Applications should contain at least a curriculum vitae and (an address to download) the bachelor's and/or master's thesis (in discrete mathematics or a related area). Please also include any further relevant information (such as publications, grades, recommendation letters, programming skills, English language certificates, GRE results). Note that the Bonn International Graduate School in Mathematics (BIGS) also offers various possibilities.