Combinatorial Optimization

Abstract

Combinatorial Optimization remains a very lively discipline with strong connections to Combinatorics, Graph Theory, Geometry, and Integer Programming. For over thirty years, Oberwolfach workshops have had a central role in shaping the field, being the unique setting where the entire spectrum of the subject is covered, from fundamental theory to practical computation. The 2008 Combinatorial Optimization Workshop was again a great success. We would like to take this opportunity to thank all speakers for the great care they put into preparing their contributions, and to thank all participants for their active discussions that led to a truly stimulating meeting. Just like our predecessors, we are happy that we could attract many of the strongest theoreticians as well as the most successful practitioners to the workshop.

Even though the team of organizers has dynamically changed over the last thirty years, a format has emerged that has been quite stable in the last decade, namely a mix of a few pre-arranged focus talks and short presentations of the participants that are scheduled during the conference. In the focus talks, selected experts survey the state-of-the-art in current hot topics and point out new mathematical challenges. While we have largely adopted this format, we have lowered the number of short presentations in favor of more time that can be spent for joint research in small groups, taking up a suggestion made by the director during the previous Combinatorial Optimization Workshop held in 2005. We have had very positive feedback from workshop participants that this measure enhances the conditions for new cooperation between participants that can be expected to lead to continued joint work and publications afterwards. Each day, the program started with a pre-arranged one hour focus presentation, followed by two thirty-minute presentations in the morning and three thirty-minute presentations before dinner.

This year's focus talks featured topics that bring together techniques from other areas of mathematics to explore new approaches for attacking well-known combinatorial problems. Tibor Jord'an led off the workshop with a talk covering methods in network localization, making use of ideas from combinatorial rigidity. Tuesday's talk was by Kazuo Murota, discussing the new area of discrete convex analysis, where combinatorial analogues of basic convex results are being developed, mainly in the Japanese research community. Friedrich Eisenbrand presented new directions in the application of techniques from the geometry of numbers in Wednesday's talk, including several new open problems in the area of integer programming. On Thursday, Monique Laurent gave an in-depth treatment of the use of semidefinite programming techniques applied to coloring problems in graphs. Andr{'a}s Seb\H{o} gave the final focus talk on Friday, describing the application of polyhedral techniques to graph optimization problems.

A new addition to this year's workshop was an evening session devoted to computational integer programming, featuring discussions led by Robert Bixby, Sanjeeb Dash, and Alexander Martin. The session highlights one of the remarkable achievements of the field in general and the Oberwolfach meetings in particular, namely, a very fast transition form basic theoretical breakthroughs to commercially successful software. Within the course of the three-year cycle of the Oberwolfach meetings, proposed new techniques work their way from academia to the leading mixed-integer programming software, delivered throughout the industrial sector. The broad mix of researchers at the Combinatorial Optimization Workshops directly contributes to this rapid transfer.