Blick ins Buch

Research Trends in Combinatorial Optimization

Bonn 2008

William J. Cook, László Lovász, Jens Vygen (Herausgeber)

Buch | Hardcover

XIII, 562 Seiten

2008 | 2009
Springer Berlin (Verlag)
978-3-540-76795-4 (ISBN)

Lese- und Medienproben

Blick ins Buch (midvox)

Artikel merken

The editors and authors dedicate this book to Bernhard Korte on the occasion of his seventieth birthday. We, the editors, are happy about the overwhelming feedback to our initiative to honor him with this book and with a workshop in Bonn on November 3-7,2008.Althoughthiswouldbeareasontolookback,wewouldratherliketolook forward and see what are the interesting research directions today. This book is written by leading experts in combinatorial optimization. All - pers were carefully reviewed, and eventually twenty-three of the invited papers were accepted for this book. The breadth of topics is typical for the eld: combinatorial optimization builds bridges between areas like combinatorics and graph theory, submodular functions and matroids, network ows and connectivity, approximation algorithms and mat- matical programming, computational geometry and polyhedral combinatorics. All these topics are related, and they are all addressed in this book. Combi- torial optimization is also known for its numerous applications. To limit the scope, however, this book is not primarily about applications, although some are mentioned at various places. Most papers in this volume are surveys that provide an excellent overview of an activeresearcharea,butthisbookalsocontainsmanynewresults.Highlightingmany of the currently most interesting research directions in combinatorial optimization, we hope that this book constitutes a good basis for future research in these areas.

László Lovász ist einer der Leiter der theoretischen Forschungsabteilung der Microsoft Corporation. Er hat 1999 den Wolf-Preis sowie den Gödel-Preis für die beste wissenschaftliche Veröffentlichung in der Informatik erhalten.

Jens Vygen ist Professor an der Universität Bonn. Seine Arbeitsgebiete sind kombinatorische Optimierung und Chip Design.

On the Location and p-Median Polytopes.- Facet Generating Techniques.- Antimatroids, Betweenness, Convexity.- Euler Complexes.- Strongly Polynomial Algorithm for the Intersection of a Line with a Polymatroid.- A Survey on Covering Supermodular Functions.- Theory of Principal Partitions Revisited.- Locally Dense Independent Sets in Regular Graphs of Large Girth-An Example of a New Approach.- Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems.- The Unbounded Knapsack Problem.- Recent Developments in Discrete Convex Analysis.- Multiflow Feasibility: An Annotated Tableau.- Many Facets of Dualities.- On the Structure of Graphs Vertex Critical with Respect to Connected Domination.- LS-LIB: A Library of Tools for Solving Production Planning Problems.- From Spheres to Spheropolyhedra: Generalized Distinct Element Methodology and Algorithm Analysis.- Graphic Submodular Function Minimization: A Graphic Approach and Applications.- Matroids-the Engineers' Revenge.- On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming.- Single-Sink Multicommodity Flow with Side Constraints.- An Introduction to Network Flows over Time.- Edge-Connectivity Augmentations of Graphs and Hypergraphs.- Some Problems on Approximate Counting in Graphs and Matroids.

Aus den Rezensionen: "Das Gebiet der kombinatorischen Optimierung umfasst ein weites Spektrum von verschiedenen mathematischen Problemen und Methoden, und ist sowohl aus praktischer als auch aus theoretischer Sicht interessant. Der praktische Nutzen ist offensichtlich, denn in fast jedem Bereich, der mathematische Methoden zur Analyse oder zur Optimierung verwendet ... treten an prominenter Stelle anspruchsvolle kombinatorische Optimierungsprobleme auf. Ein innermathematisch reizvoller Aspekt wird im Vorwort des rezensierten Buches schön beschrieben ... Insgesamt kann man konstatieren, daß das Buch unbedingt zu empfehlen ist für alle ..." (Thomas Kalinowski, in: RHO Mathematik Verein www.math.uni-rostock.de/rho, September/2009)

Aus den Rezensionen:

“Das Gebiet der kombinatorischen Optimierung umfasst ein weites Spektrum von verschiedenen mathematischen Problemen und Methoden, und ist sowohl aus praktischer als auch aus theoretischer Sicht interessant. Der praktische Nutzen ist offensichtlich, denn in fast jedem Bereich, der mathematische Methoden zur Analyse oder zur Optimierung verwendet ... treten an prominenter Stelle anspruchsvolle kombinatorische Optimierungsprobleme auf. Ein innermathematisch reizvoller Aspekt wird im Vorwort des rezensierten Buches schön beschrieben ... Insgesamt kann man konstatieren, daß das Buch unbedingt zu empfehlen ist für alle ...“ (Thomas Kalinowski, in: RHO Mathematik Verein www.math.uni-rostock.de/rho, September/2009)

Erscheint lt. Verlag	5.11.2008
Zusatzinfo	XIII, 562 p.
Verlagsort	Berlin
Sprache	englisch
Maße	155 x 235 mm
Themenwelt	Mathematik / Informatik ► Mathematik ► Graphentheorie
Themenwelt	Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
Schlagworte	algorithms • Calculus • combinatorial optimization • combinatorics • Complexity • Discrete Mathematics • Mathematical Programming • Mathematics of Computing • Operations Research • Optimization • Partition • theoretical computer science
ISBN-10	3-540-76795-9 / 3540767959
ISBN-13	978-3-540-76795-4 / 9783540767954
Zustand	Neuware