

1995  PhD in Computer Science, HU Berlin  1994  2004  Assistant Professor (C1), HU Berlin  2004  Habilitation in Computer Science, HU Berlin  2002  2007  Project leader Complex Networks, DFG Research Center Matheon, Berlin  2004  2005  Visiting Professor of Algorithmic Discrete Mathematics, TU Berlin  2005  2006  Assistant Professor (C2), HU Berlin  2006  2007  Visiting Professor of Algorithms and Complexity, HU Berlin  Since 2007  Professor (W2), University of Bonn 


My main area of research is combinatorial optimization and its applications in chip design. One of the most famous problems in combinatorial optimization is the traveling salesman problem. This problem is NPhard and the best approximation algorithm currently known is due to Christofides from 1976. Recently we were able to exactly estimate the approximation ratio of the greedy algorithm for the traveling salesman problem. This was an open question for more than 35 years. Moreover we proved that the integrality ratio of the subtour LP for the Traveling Salesman Problem has value at least 4/3 in case of Euclidean instances. This result sheds new light on the famous 4/3 conjecture for the Traveling Salesman Problem. We also proposed a new algorithm that allows to find exact solutions to large Traveling Salesman Problems up to ten times faster than the best algorithms so far. Motivated by an application in chip design we designed a linear time algorithm to pack a set of squares into a rectangle. Our algorithm leaves much less wasted space than the so far best known algorithm. Moreover we devised exact algorithms for several problems in chip design, e.g. for packing rectangles into an area minimal rectangle or for finding netlength minimal placements of macros. In many cases our algorithms are several orders of magnitudes faster than existing algorithms.
One of the main challenges is to improve on Christofides approximation algorithm from 1976 for the Traveling Salesman Problem. One possible way to attack this problem is to prove the so called 4/3 conjecture which states that the integrality ratio of the subtour LP is 4/3. Recent progress that has been made on special cases of this conjecture seems to be promising. We think that proving the 4/3 conjecture in the special case of Euclidean instances could be a feasible goal. We recently proved that in this case 4/3 is a lower bound. For Euclidean TSP a proof of the 4/3 conjecture would not improve on the best known approximation ratio as in this case even a polynomial time approximation scheme is known. In the area of chip design a main challenge is to design algorithms that simultaneously optimize several objective functions. Due to the complexity of such problems one usually iteratively optimizes one objective function after the other in several rounds. Algorithms that allow to optimize several such objectives functions in one step would not only improve the running time but also the quality of results.


DFG Research Center Matheon, “Complex Networks”
Project leader, 2002  2007
“Combinatorial Optimization and Chip Design”, longterm cooperation funded by IBM Corporation
since 2007


Research Area KL My main research area is combinatorial optimization with a focus on approximation algorithms, exact algorithms and applications in chip design [1]. The best studied problems in combinatorial optimization are the traveling salesman problem and the Steiner tree problem. We contributed several results to both problems. It was a long standing open problem to determine the approximation ratio of the greedy algorithm for the traveling salesman problem. We completely solve this problem [2]. Moreover, we provide new lower bounds on the approximation ratio of the nearest neighbor heuristic for euclidean and rectilinear traveling salesman problems [3]. An open conjecture states that the integrality gap of the subtour LP is 4/3 for the metric traveling salesman problem. It is well known, that 4/3 is a lower bound. We were able to prove that this lower bound also holds in the special case of the euclidean traveling salesman problem [4]. We also developed a new approach that speeds up the exact solution of large traveling salesman problems up to a factor of 10x [5]. For the Steiner tree problem in graphs we developed a new exact algorithm that is significantly faster than existing algorithms on many instance classes [6].
Motivated by the placement problem in chip design we studied the problem of packing a set of rectangles into a rectangular area. We obtained the best known bound on packing squares into a rectangle [7] and also developed a new algorithm for the rectangle packing problem [8]. This algorithm is able to solve several benchmark problems that were unsolved before.
In chip design we not only have to pack rectangles into a rectangular area but we have to find a packing that optimizes the total wirelength of such a packing. We proposed new exact algorithms for solving this problem [9,10] that for the first time are able to solve instances of reasonable sizes. We also designed a set of algorithms, called BonnCell, that are able to find optimum solutions to the Leaf Cell Layout problem in Chip design [11,12]. These algorithms are the only existing algorithms for solving this problem exactly and are heavily used in industry. 


[ 1] Stephan Held, Stefan Hougardy, Jens Vygen
Chip design Princeton Companion on Applied Mathematics Publisher: Princeton University Press 2015[ 2] Judith Brecklinghaus, Stefan Hougardy
The approximation ratio of the greedy algorithm for the metric traveling salesman problem Oper. Res. Lett. , 43: (3): 259261 2015 DOI: 10.1016/j.orl.2015.02.009[ 3] Stefan Hougardy, Mirko Wilde
On the nearest neighbor rule for the metric traveling salesman problem Discrete Appl. Math. , 195: : 101103 2015 DOI: 10.1016/j.dam.2014.03.012[ 4] Stefan Hougardy
On the integrality ratio of the subtour LP for Euclidean TSP Oper. Res. Lett. , 42: (8): 495499 2014 DOI: 10.1016/j.orl.2014.08.009[ 5] Stefan Hougardy, Rasmus T. Schroeder
Edge elimination in TSP instances Graphtheoretic concepts in computer science of Lecture Notes in Comput. Sci. : 275286 Publisher: Springer, Cham 2014 DOI: 10.1007/9783319123400_23[ 6] Stefan Hougardy, Jannik Silvanus, Jens Vygen
Dijkstra meets Steiner: a fast exact goaloriented Steiner tree algorithm Math. Program. Comput. , 9: (2): 135202 2017 DOI: 10.1007/s1253201601101[ 8] Stefan Hougardy
A Scale Invariant Algorithm for Packing Rectangles Perfectly Proceedings of the fourth International Workshop on Bin Packing andPlacement Constraints (BPPC'12) 2012[ 9] Julia Funke, Stefan Hougardy, Jan Schneider
Wirelength Optimal Rectangle Packings Proceedings of the fourth International Workshop on Bin Packing andPlacement Constraints (BPPC'12) 2012[ 11] Stefan Hougardy, Tim Nieberg, Jan Schneider
BonnCell: Automatic Layout of Leaf Cells Proceedings of the 18th Asia and South Pacific Design AutomationConference (ASPDAC) 2013 2013[ 12] Pascal Cremer, Stefan Hougardy, Jan Schneider, Jannik Silvanus
Automatic Cell Layout in the 7nm Era ISPD '17 Proceedings of the 2017 ACM International Symposium on PhysicalDesign 2017[ 13] Doratha E. Drake Vinkemeier, Stefan Hougardy
A lineartime approximation algorithm for weighted matchings in graphs ACM Trans. Algorithms , 1: (1): 107122 2005 DOI: 10.1145/1077464.1077472[ 14] Doratha E. Drake, Stefan Hougardy
A simple approximation algorithm for the weighted matching problem Inform. Process. Lett. , 85: (4): 211213 2003 DOI: 10.1016/S00200190(02)003939[ 15] Stefan Hougardy, Hans JÃ¼rgen PrÃ¶mel
A 1.598 approximation algorithm for the Steiner problem in graphs Proceedings of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms (Baltimore, MD, 1999) Publisher: ACM, New York 1999[ 16] Thomas EmdenWeinert, Stefan Hougardy, Bernd Kreuter
Uniquely colourable graphs and the hardness of colouring graphs of large girth Combin. Probab. Comput. , 7: (4): 375386 1998 DOI: 10.1017/S0963548398003678[ 17] Stefan Hougardy, Jannik Silvanus, Jens Vygen
Dijkstra meets Steiner: a fast exact goaloriented Steiner tree algorithm Mathematical Programming Computation , 9: (2): 135202 2017





2008  Professor (W2), RWTH Aachen 


 Master theses: 17, currently 5
 Diplom theses: 24
 PhD theses: 7, currently 3


Download Profile 