Algorithms and Combinatorics Volume 21 EditorialBoard R.L.Graham,LaJolla B.Korte,Bonn L.Lovász,Budapest A.Wigderson,Princeton G.M.Ziegler,Berlin Bernhard Korte · Jens Vygen Combinatorial Optimization Theory and Algorithms Fourth Edition 123 BernhardKorte JensVygen ResearchInstituteforDiscreteMathematics UniversityofBonn Lennéstraße2 53113Bonn Germany [email protected] [email protected] ISBN 978-3-540-71843-7 e-ISBN 978-3-540-71844-4 DOI 10.1007/978-3-540-71844-4 AlgorithmsandCombinatoricsISSN0937-5511 LibraryofCongressControlNumber:2007936375 MathematicsSubjectClassification(2000):90C27,68R10,05C85,68Q25 ©2008Springer-VerlagBerlinHeidelberg Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation,broadcasting, reproductiononmicrofilmorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9, 1965,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violations areliabletoprosecutionundertheGermanCopyrightLaw. Theuseofgeneral descriptive names, registered names, trademarks, etc. inthis publication does not imply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotective lawsandregulationsandthereforefreeforgeneraluse. Typesetting:bytheauthorsusingaSpringerTEXmacropackage Production:LE-TEXJelonek,Schmidt&VöcklerGbR,Leipzig Coverdesign:WMXDesignGmbH,Heidelberg Printedonacid-freepaper 987654321 springer.com Preface to the Fourth Edition WithfourEnglisheditions,andtranslationsintofourotherlanguagesforthcoming, we are very happy with the development of our book. Again, we have revised, updated,andsignificantlyextendeditforthisfourthedition.Wehaveaddedsome classical material that may have been missed so far, in particular on linear pro- gramming,thenetworksimplexalgorithm,andthemax-cutproblem.Wehavealso added a number of new exercises and up-to-date references. We hope that these changes serve to make our book an even better basis for teaching and research. We gratefully acknowledge the continuous support of the Union of the Ger- man Academies of Sciences and Humanities and the NRW Academy of Sciences via the long-term research project “Discrete Mathematics and Its Applications”. We also thank those who gave us feedback on the third edition, in particular Takao Asano, Christoph Bartoschek, Bert Besser, Ulrich Brenner, Jean Fonlupt, SatoruFujishige,MarekKarpinski,JensMaßberg,DenisNaddef,SvenPeyer,Klaus Radke, Rabe von Randow, Dieter Rautenbach, Martin Skutella, Markus Struzyna, Ju¨rgen Werber, Minyi Yue, and Guochuan Zhang, for their valuable comments. At http://www.or.uni-bonn.de/∼vygen/co.html we will continue to maintain updated information about this book. Bonn, August 2007 Bernhard Korte and Jens Vygen Preface to the Third Edition After five years it was time for a thoroughly revised and substantially extended edition.Themostsignificantfeatureisacompletelynewchapteronfacilitylocation. No constant-factor approximation algorithms were known for this important class ofNP-hardproblemsuntileightyearsago.Todaythereareseveralinterestingand verydifferenttechniquesthatleadtogoodapproximationguarantees,whichmakes this area particularly appealing, also for teaching. In fact, the chapter has arisen from a special course on facility location. Many of the other chapters have also been extended significantly. The new materialincludesFibonacciheaps,Fujishige’snewmaximumflowalgorithm,flows over time, Schrijver’s algorithm for submodular function minimization, and the Robins-ZelikovskySteinertreeapproximationalgorithm.Severalproofshavebeen streamlined, and many new exercises and references have been added. We thank those who gave us feedback on the second edition, in particular Takao Asano, Yasuhito Asano, Ulrich Brenner, Stephan Held, Tomio Hirata, Dirk Mu¨ller, Kazuo Murota, Dieter Rautenbach, Martin Skutella, Markus Struzyna and Ju¨rgen Werber, for their valuable comments. Eminently, Takao Asano’s notes and Ju¨rgenWerber’s proofreadingofChapter22 helpedtoimprovethe presentationat various places. Again we would like to mention the Union of the German Academies of Sciences and Humanities and the Northrhine-Westphalian Academy of Sciences. Their continuous support via the long-term project “Discrete Mathematics and Its Applications” funded by the German Ministry of Education and Research and the State of Northrhine-Westphalia is gratefully acknowledged. Bonn, May 2005 Bernhard Korte and Jens Vygen Preface to the Second Edition It was more than a surprise to us that the first edition of this book already went out of print about a year after its first appearance. We were flattered by the many positiveandevenenthusiasticcommentsandlettersfromcolleaguesandthegeneral readership. Several of our colleagues helped us in finding typographical and other errors. In particular, we thank Ulrich Brenner, Andra´s Frank, Bernd Ga¨rtner and Rolf Mo¨hring. Of course, all errors detected so far have been corrected in this second edition, and references have been updated. Moreover, the first preface had a flaw. We listed all individuals who helped us in preparing this book. But we forgot to mention the institutional support, for which we make amends here. It is evident that a book project which took seven years benefited from many different grants. We would like to mention explicitly the bilateral Hungarian- German Research Project, sponsored by the Hungarian Academy of Sciences and the Deutsche Forschungsgemeinschaft, two Sonderforschungsbereiche (special re- search units) of the Deutsche Forschungsgemeinschaft, the Ministe`re Franc¸ais de la Recherche et de la Technologie and the Alexander von Humboldt Foundation for support via the Prix Alexandre de Humboldt, and the Commission of the Eu- ropean Communities for participation in two projects DONET. Our most sincere thanks go to the Union of the German Academies of Sciences and Humanities and to the Northrhine-Westphalian Academy of Sciences. Their long-term project “Discrete Mathematics and Its Applications” supported by the German Ministry of Education and Research (BMBF) and the State of Northrhine-Westphalia was of decisive importance for this book. Bonn, October 2001 Bernhard Korte and Jens Vygen