Combinatorial Optimization (CO)

Combinatorial Optimization

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.

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.