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

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


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.

Selected Publications

[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): 259--261
2015
[3] Stefan Hougardy, Mirko Wilde
On the nearest neighbor rule for the metric traveling salesman problem
Discrete Appl. Math. , 195: : 101--103
2015
[4] Stefan Hougardy
On the integrality ratio of the subtour LP for Euclidean TSP
Oper. Res. Lett. , 42: (8): 495--499
2014
[5] 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
[6] Stefan Hougardy, Jannik Silvanus, Jens Vygen
Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
Math. Program. Comput. , 9: (2): 135--202
2017
[7] Stefan Hougardy
On packing squares into a rectangle
Comput. Geom. , 44: (8): 456--463
2011
[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
[10] 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
[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 linear-time approximation algorithm for weighted matchings in graphs
ACM Trans. Algorithms , 1: (1): 107--122
2005
[14] Doratha E. Drake, Stefan Hougardy
A simple approximation algorithm for the weighted matching problem
Inform. Process. Lett. , 85: (4): 211--213
2003
[15] 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
[16] 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
[17] 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

Publication List

MathSciNet Publication List (external link)

Offers

2008

Professor (W2), RWTH Aachen

Supervised Theses

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