Combinatorial Optimization (CO)

Combinatorial Optimization: prof.dr.ir. G.J. Woeginger, prof.dr. N. Bansal, dr.ir. C.A.J. Hurkens, dr. J.C.M. Keijsper, dr. J. Nederlof, dr. R.A. Pendavingh

The group focuses on the analysis and solution of discrete algorithmic problems that are computationally difficult (NP-hard). A generic formulation of such problems is: given a number of boundary conditions and constraints, find a solution that minimizes the cost or maximizes the profit.

Some of our research is of a fundamental nature, but most of it is inspired by real-world
problems. Typical application areas are telecommunication, logistics, production planning,
and health care. In these areas we form one of the leading groups in the world, and our research is published in the top-journals of the field.

Group leader: Prof.dr.ir. Gerhard J. Woeginger

Gerhard Woeginger received a diploma degree in mathematics from the Technical University of Graz (Austria) in 1988, and a Ph.D. degree in 1991 and a habilitation degree in 1995 from the same university. He has worked at the TU Graz, the Free University Berlin, and the University of Twente, before moving to Eindhoven in 2004.

His research area is discrete optimization and algorithmics, and in particular scheduling theory and parameterized and exact computation. In 2004 he obtained a prestigious VICI grant for his research from the Netherlands Organization for Scientific Research (NWO).

He has authored over 300 scientific papers. He currently serves on the editorial boards of eight
peer-reviewed journals, and he is a member of the council of the European Association for Theoretical Computer Science (EATCS) and of the steering committee of the Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP). 

Key publications

1. H. van der Holst and R.A. Pendavingh (2009). On a graph property generalizing planarity and flatness. Combinatorica 29, 337-361.

2. R.A. Pendavingh and S.H.M. van Zwam (2007). New Korkin-Zolotarev inequalities. SIAM Journal on Optimization 18, 364-378.

3. G. Post and G.J. Woeginger (2006).  Round-robin tournaments, home-away assignments, and the break minimization problem.  Discrete Optimization 3, 165-173.

4. P. Csorba, C.A.J. Hurkens, and G.J. Woeginger (2010). The Alcuin number of a graph and its connections to the vertex cover number. SIAM Journal on Discrete Mathematics 24, 757-769.

5. A. Barvinok, S. Fekete, D.S. Johnson, A. Tamir, G.J. Woeginger, and R. Woodroofe.  The geometric maximum travelling salesman problem. Journal of the ACM 50, 641-664.