

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


Former Research Area K Algorithms for large scale optimization problems need to be highly efficient. The usual notion of efficient algorithms is that their running time is polynomial. However, for most problems as they appear for example in the area of VLSI design, even quadratic running time is already too costly. We therefore studied approximation algorithms with almost linear running time. A major contribution was a linear time 2/3 approximation algorithm for the matching problem [1]. We were able to obtain similar results for the more general degree constrained subgraph problem [2] and also provided an efficient parallel approximation algorithm [3]. Recently we were able to provide a linear time approximation algorithm for the problem of packing squares into a rectangle [4], which is motivated by the placement problem in VLSI design. Our new algorithm is not only the fastest algorithm for solving this problem but in addition yields the currently best known approximation ratio. 


[ 1] 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[ 2] Stefan Hougardy
Linear time approximation algorithms for degree constrained subgraph problems Research trends in combinatorial optimization Publisher: Springer, Berlin 2009 DOI: 10.1007/9783540767961_9[ 3] Stefan Hougardy, Doratha E. Vinkemeier
Approximating weighted matchings in parallel Inform. Process. Lett. , 99: (3): 119123 2006 DOI: 10.1016/j.ipl.2006.03.005[ 4] Stefan Hougardy
On packing squares into a rectangle Comput. Geom. , 44: (8): 456463 2011 DOI: 10.1016/j.comgeo.2011.05.001[ 5] 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[ 6] 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[ 7] 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[ 8] 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[ 9] 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[ 10] 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[ 11] J. Funke, S. Hougardy, J. Schneider
An exact algorithm for wirelength optimal placements in VLSI design Integration, the VLSI Journal , 52: : 355366 2016 DOI: http://dx.doi.org/10.1016/j.vlsi.2015.07.001[ 12] Ryan B. Hayward, Stefan Hougardy, Bruce A. Reed
Polynomial time recognition of P 4structure Symposium on Discrete Algorithms: Proceedings of the thirteenth annual ACMSIAM symposium on Discrete algorithms 6 (08): 382389 2002



2008  Professor (W2), RWTH Aachen 


 Master theses: 14, currently 4
 Diplom theses: 24
 PhD theses: 7, currently 3


Download Profile 