|
|
|
| 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 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.
|
|
DFG Research Center Matheon, “Complex Networks”
Project leader, 2002 - 2007
“Combinatorial Optimization and Chip Design”, long-term cooperation funded by IBM Corporation
since 2007
|
|
[ 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
2015
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
2014
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
2014
DOI: 10.1016/j.orl.2014.08.009[ 5] 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[ 6] 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[ 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
1999[ 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
1998
DOI: 10.1017/S0963548398003678[ 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
2017 |
|
|
|
|
|
|
|
| 2008 | Professor (W2), RWTH Aachen |
|
|
- Master theses: 28, currently 4
- Diplom theses: 24
- PhD theses: 9, currently 3
|
|
Download Profile  |
