This comprehensive textbook on combinatorial optimization places special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It is based on numerous courses on combinatorial optimization and specialized topics, mostly at graduate level. This book reviews the fundamentals, covers the classical topics (paths, flows, matching, matroids, NP-completeness, approximation algorithms) in detail, and proceeds to advanced and recent topics, some of which have not appeared in a textbook before. Throughout, it contains complete but concise proofs, and also provides numerous exercises and references. This sixth edition has again been updated, revised, and significantly extended. Among other additions, there are new sections on shallow-light trees, submodular function maximization, smoothed analysis of the knapsack problem, the (ln 4+e)-approximation for Steiner trees, and the VPN theorem. Thus, this book continues to represent the state of the art of combinatorial optimization.

This comprehensive textbook on combinatorial optimization places special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It is based on numerous courses on combinatorial optimization and specialized topics, mostly at graduate level. This book reviews the fundamentals, covers the classical topics (paths, flows, matching, matroids, NP-completeness, approximation algorithms) in detail, and proceeds to advanced and recent topics, some of which have not appeared in a textbook before. Throughout, it contains complete but concise proofs, and also provides numerous exercises and references. This sixth edition has again been updated, revised, and significantly extended. Among other additions, there are new sections on shallow-light trees, submodular function maximization, smoothed analysis of the knapsack problem, the (ln 4+e)-approximation for Steiner trees, and the VPN theorem. Thus, this book continues to represent the state of the art of combinatorial optimization.

Oh cieca cupidigia, oh ira folie, Che si ci sproni nella vita corta, E nell' eterna poi si mal c'immolle! o blind greediness and foolish rage, That in our fleeting life so goads us on And plunges us in boiling blood for ever! Dante, The Divine Comedy Inferno, XII, 17, 49/51. On an afternoon hike during the second Oberwolfach conference on Mathematical Programming in January 1981, two of the authors of this book discussed a paper by another two of the authors (Korte and Schrader [1981]) on approximation schemes for optimization problems over independence systems and matroids. They had noticed that in many proofs the hereditary property of independence systems and matroids is not needed: it is not required that every subset of a feasible set is again feasible. A much weaker property is sufficient, namely that every feasible set of cardinality k contains (at least) one feasible subset of cardinality k - 1. We called this property accessibility, and that was the starting point of our investigations on greedoids.

This volume constitutes the proceedings of the workshop "Optimierung und Operations Research", held at the Elly Holterhoff Backing Stift (Bad Honnef) of the University of Bonn, October 2-8, 1977. This conference was devoted to recent advances in the field of mathe- matical programming, optimization techniques, and operations research. It was attended by about 50 invited participants. Furthermore many scholars in these areas showed a great interest in this workshop, despite several other conferences and activities on similar topics in the year 1977. The organizers regret that considerations of avail- able space for conference activities limited the number of participants. This widespread interest, the high quality of the lectures presented and the active and stimulating discussions at the conference mani- fested the breadth of the activity ongoing in the field covered by this workshop and the necessity that this field be cultivated to a greater extent by the scientific community. The workshop was organized by the Institute of Operations Research (Sonderforschungsbereich 21), University of Bonn and was generously sponsored by the Gesellschaft der Freunde und Forderer der Rheinischen Friedrich-Wilhelms-Universitat and by IBM Germany. Only through this invaluable support was this workshop possible; for this the editors wish to express their sincere thanks and appreciation. Bonn, December 1977 R. Henn B. Korte W. Oettli III TABLE OF CONTENTS A. Bachem The theorem of Minkowski for polyhedral monoids and aggregated linear diophantine systems * * * . * * * * * * * S. Baum and L.E. Trotter, Jr.

Now fully updated in a third edition, this is a comprehensive textbook on combinatorial optimization. It puts special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. The book contains complete but concise proofs, also for many deep results, some of which have not appeared in print before. Recent topics are covered as well, and numerous references are provided. This third edition contains a new chapter on facility location problems, an area which has been extremely active in the past few years. Furthermore there are several new sections and further material on various topics. New exercises and updates in the bibliography were added.

Die vorliegende Arbeit ist ein in sich abgeschlossenes Teilergebnis eines von mir geleiteten Forschungsvorhabens, das die Untersuchung und Analyse der wirtschaft- lichen Entwicklungsproblematik mit dem Ziel einer Erweiterung der Einsicht in die Grundsatze und Richtlinien fur die praktische Wirtschafts- und Finanzpolitik zum Gegenstand hat. Diese Arbeit setzt in speziell mathematischer Ausrichtung meine Untersuchungen uber das Konjunkturphiinomen (siehe hierzu insbesondere M. E. KAMP, D. SMOLINSKI und H. ]. WILD, Untersuchungen zur endogenen ProzeBsystematik der marktwirtschaft- lichen Entwicklung im 20. Jahrhundert, Stuttgart 1964) fort, wobei die bisherigen Resultate mir den Mut gaben, auf der Basis der dort gewonnenen Erkenntnisse der okonomischen Phanornenzusammenhange, ein Prognosernodell entwickeln zu lassen. Hierbei handelt es sich urn ein sogenanntes univariables Modell, das irn Gegensatz zu den okonomischen Globalrnodellen zur Analyse und Prognose explizit keine weiteren okonomischen Variablen benutzt. Es wird vielrnehr die V orhersage der Entwicklung okonomischer GroBen aus den analytisch festgestellten GesetzmaBigkeiten in den Bewegungsablaufen der Vergangenheit vorgenommen. Ober die mit einem solchen Ansatz zu erreichende Prognosegute gibt das umfangreiche Zahlenmaterial, welches von den Verfassern in Kapitel 6 zusammengestellt wurde, einen ausfiihrlichen Einblick. Das hier dargestellte Verfahren kann und soll unmittelbar keinen Beitrag zur okonorni- schen Theorienbildung leisten. Es solI nur, von dem ausgehend, was als okonomische Entwicklung begrifflich und tatsachlich vorliegt, eine exakte instrurnentelle Grundlage sein, von der her bestehende Hypothesen zur okonomischen Entwicklungsproblernatik bestatigt oder falsifiziert oder gar ncu konzipiert werden konnen.

Das umfassende Lehrbuch zur Kombinatorischen Optimierung beruht auf Vorlesungen, die die Autoren an der Universitat Bonn gehalten haben. Sie geben den neuesten Stand des Fachgebiets wieder - mit Schwerpunkt auf theoretischen Resultaten und Algorithmen mit guten Laufzeiten und Ergebnissen. Der Band enthalt vollstandige Beweise, einige davon wurden bisher nicht in der Lehrbuchliteratur publiziert. Die deutschsprachige Neuauflage enthalt alle Erganzungen und Aktualisierungen der 5. englischsprachigen Auflage, darunter mehr als 60 neue UEbungsaufgaben.