Professor Dr.

Stephan Held

Kombinatorische Optimierung
von der Theorie zur Anwendung.

Chipdesign · Graphenfärbung · Tourenplanung

Kontakt

Forschungsinstitut für Diskrete Mathematik
Lennéstr. 2 · 53113 Bonn · Deutschland
Büro: Raum 303
held@dm.uni-bonn.de
+49 228 738740

Arbeitsgebiete

VLSI-Design
- Ich arbeite an unterschiedlichen Themen häufig in Kollaboration mit 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 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 einer der schnellsten open-source Branch-and-Price Codes zu diesem Problem. ZykovColor leverages incremental SAT-Solving to tackle the problem.

Ich bin associate Editor bei Discrete Optimization.

Publikationen

M. Drees, S. Held, and E.Perner: Simple Electrostatic Global Placement without Filler Cells. Accepted for ISPD 2027.
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.

Konferenzen & Schulen

International Symposium on Physical Design, years: 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.

Stephan Held

Kontakt

Arbeitsgebiete

Publikationen

Konferenzen & Schulen

Lehre