Combinatorial Optimization (CO)

Combinatorial Optimization

Our group focuses on combinatorial optimization. We investigate the structure of such problems, analyze the relations between different problems, and use this knowledge to design efficient and effective algorithms for solving them. We study both exact and heuristic algorithms. We are also interested in combinatorial optimization problems where the input is revealed only gradually, or where there is uncertainty in the parameters, leading to online, stochastic or robust solution methods. We develop theoretic results, for instance in graph theory and matroids, and apply these to real-world situations. Typical application areas are scheduling, production planning, logistics, network design, communication and routing in networks, and health care.

We have open PhD positions in the area of combinatorial optimization. Applicants should have a strong analytical background and interest. Applications, and/or further information can be directed to Frits Spieksma.

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.