Prof. Dr. Stefan Hougardy

E-mail: hougardy(at)
Phone: +49 228 73 8770
Institute: Research Institute for Discrete Mathematics
Research Area: Research Area C3

Academic Career


PhD in Computer Science, HU Berlin

1994 - 2004

Assistant Professor (C1), HU Berlin


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

Research Profile

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 NP-hard 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.

Research Projects and Activities

DFG Research Center Matheon, “Complex Networks”
Project leader, 2002 - 2007

“Combinatorial Optimization and Chip Design”, long-term cooperation funded by IBM Corporation
since 2007

Selected Publications

[1] Judith Brecklinghaus, Stefan Hougardy
The approximation ratio of the greedy algorithm for the metric traveling salesman problem
Oper. Res. Lett. , 43: (3): 259--261
DOI: 10.1016/j.orl.2015.02.009
[2] Stefan Hougardy, Rasmus T. Schroeder
Edge elimination in TSP instances
Graph-theoretic concepts in computer science
of Lecture Notes in Comput. Sci. : 275--286
Publisher: Springer, Cham
DOI: 10.1007/978-3-319-12340-0_23
[3] Stefan Hougardy
On the integrality ratio of the subtour LP for Euclidean TSP
Oper. Res. Lett. , 42: (8): 495--499
DOI: 10.1016/j.orl.2014.08.009
[4] Stefan Hougardy
On packing squares into a rectangle
Comput. Geom. , 44: (8): 456--463
DOI: 10.1016/j.comgeo.2011.05.001
[5] Doratha E. Drake Vinkemeier, Stefan Hougardy
A linear-time approximation algorithm for weighted matchings in graphs
ACM Trans. Algorithms , 1: (1): 107--122
DOI: 10.1145/1077464.1077472
[6] Doratha E. Drake, Stefan Hougardy
A simple approximation algorithm for the weighted matching problem
Inform. Process. Lett. , 85: (4): 211--213
DOI: 10.1016/S0020-0190(02)00393-9
[7] Stefan Hougardy, Hans Jürgen Prömel
A 1.598 approximation algorithm for the Steiner problem in graphs
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 1999)
Publisher: ACM, New York
[8] Thomas Emden-Weinert, Stefan Hougardy, Bernd Kreuter
Uniquely colourable graphs and the hardness of colouring graphs of large girth
Combin. Probab. Comput. , 7: (4): 375--386
DOI: 10.1017/S0963548398003678
[9] J. Funke, S. Hougardy, J. Schneider
An exact algorithm for wirelength optimal placements in VLSI design
Integration, the VLSI Journal , 52: : 355--366
[10] Stefan Hougardy, Jannik Silvanus, Jens Vygen
Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
Mathematical Programming Computation , 9: (2): 135--202

Publication List

MathSciNet Publication List (external link)

ArXiv Preprint List (external link)



Professor (W2), RWTH Aachen

Supervised Theses

  • Master theses: 28, currently 4
  • Diplom theses: 24
  • PhD theses: 9, currently 3
Download Profile