Avant-propos à la cinquème édition originale

1En préparant la première édition de ce livre, il y a plus de dix ans, nous avons voulu atteindre deux objectifs : écrire un traité pour des enseignements de niveau avancé et écrire un livre de référence pour la recherche. À l’occasion de chaque nouvelle édition nous nous sommes demandé comment améliorer l’ouvrage, sachant qu’il est de plus en plus délicat de décrire de manière intelligible cette discipline en croissance permanente.

2Si nous avions inclus tout ce que nous souhaitions développer, plus d’un volume aurait été nécessaire. Comme ce livre est utilisé dans de nombreux enseignements, parfois même au niveau licence, nous avons pensé qu’il était préférable d’ajouter des résultats classiques plutôt que d’inclure une sélection de nouveaux résultats.

3Dans cette édition, nous avons ajouté une preuve de la formule de Cayley ainsi que plus de détails sur les flots, un nouvel algorithme plus rapide pour le b-couplage, un schéma d’approximation pour le problème du sac à dos multidimensionnel, et des résultats sur le ratio flot-max coupe-min pour le multiflot et pour le problème de la coupe dispersée. Il y a aussi de nombreuses améliorations et plus de soixante nouveaux exercices. Nous avons également mis à jour les références afin de présenter les résultats les plus récents et nous avons corrigé quelques erreurs mineures.

4Nous voudrions remercier Takao Asano, Maxim Babenko, Ulrich Brenner, Benjamin Bolten, Christoph Buchheim, Jean Fonlupt, András Frank, Michael Gester, Stephan Held, Stefan Hougardy, Hirosh Iida, Klaus Jensen, Alexander Karzanov, Levin Keller, Alexander Kleff, Niko Klewinghaus, Stefan Knauf, Barbara Langfeld, Jens Maßberg, Marc Pfetsch, Klaus Radke, Rabe von Randow, Tomás Salles, Jan Schneider, Christian Schulte, Andras Sebő, Martin Skutella, Jácint Szabó et Simon Wedekind pour leurs précieux retours sur les éditions précédentes.

5Nous sommes heureux que ce livre ait reçu un si bon accueil et que de nouvelles traductions soient prévues. Des traductions de l’ouvrage en japonais, français, italien, allemand, russe et chinois sont parues depuis 2009 ou sont sur le point de paraître. Nous espérons que ce livre continuera à remplir ses objectifs pour l’enseignement et la recherche en optimisation combinatoire.

6Bonn, septembre 2011