Stephan Held:
[English Homepage]
Deutsche Homepage
[Arbeitsgebiete]
[Publikationen]
[Konferenzen & Schulen]
[Lehre]
[Studierende]
Adresse:
Professor Dr. Stephan Held
Forschungsinstitut für Diskrete Mathematik
Universität Bonn
Lennéstr. 2
53113 Bonn
Deutschland
E-Mail: held@dm.uni-bonn.de
Phone: +49 228 738740
Büro: Raum 303
- VLSI-Design
- Graph Coloring: exactcolors einer der schnellsten open-source Codes zu diesem Problem.
- Vehicle Routing:
Ich bin associate Editor bei Discrete Optimization.
- 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.
- International Symposium on Physical Design, years: 2023-2027
- Bonn Worksh 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.