Profile
Profile

Prof. Dr. Stefan Hougardy

E-mail: hougardy(at)or.uni-bonn.de
Phone: +49 228 73 8770
Homepage: http://www.or.uni-bonn.de/~hougardy/
Institute: Research Institute for Discrete Mathematics
Research Areas: Research Area KL
Former Research Area K
Mathscinet-Number: 338593

Academic Career

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

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

Contribution to Research Areas

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.

Selected Publications

[1] Doratha E. Drake Vinkemeier, Stefan Hougardy
A linear-time approximation algorithm for weighted matchings in graphs
ACM Trans. Algorithms , 1: (1): 107--122
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/978-3-540-76796-1_9
[3] Stefan Hougardy, Doratha E. Vinkemeier
Approximating weighted matchings in parallel
Inform. Process. Lett. , 99: (3): 119--123
2006
DOI: 10.1016/j.ipl.2006.03.005
[4] Stefan Hougardy
On packing squares into a rectangle
Comput. Geom. , 44: (8): 456--463
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): 259--261
2015
DOI: 10.1016/j.orl.2015.02.009
[6] 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
2014
DOI: 10.1007/978-3-319-12340-0_23
[7] Stefan Hougardy
On the integrality ratio of the subtour LP for Euclidean TSP
Oper. Res. Lett. , 42: (8): 495--499
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): 211--213
2003
DOI: 10.1016/S0020-0190(02)00393-9
[9] 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
1999
[10] 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
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: : 355--366
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 4-structure
Symposium on Discrete Algorithms: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms
6 (08): 382--389
2002

Publication List

Offers

2008

Professor (W2), RWTH Aachen

Supervised Theses

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