Research trends in combinatorial optimization: Bonn 2008

Mourad Baïou, Francisco Barahona (auth.), William Cook, László Lovász, Jens Vygen (eds.)9783540767954, 3540767959

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.

---

Table of contents :
Front Matter….Pages i-xviii
On the Location and p -Median Polytopes….Pages 1-31
Facet Generating Techniques….Pages 33-55
Antimatroids, Betweenness, Convexity….Pages 57-64
Euler Complexes….Pages 65-68
Strongly Polynomial Algorithm for the Intersection of a Line with a Polymatroid….Pages 69-85
A Survey on Covering Supermodular Functions….Pages 87-126
Theory of Principal Partitions Revisited….Pages 127-162
Locally Dense Independent Sets in Regular Graphs of Large Girth—An Example of a New Approach….Pages 163-183
Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems….Pages 185-200
The Unbounded Knapsack Problem….Pages 201-217
Recent Developments in Discrete Convex Analysis….Pages 219-260
Multiflow Feasibility: An Annotated Tableau….Pages 261-283
Many Facets of Dualities….Pages 285-302
On the Structure of Graphs Vertex Critical with Respect to Connected Domination….Pages 303-315
LS-LIB: A Library of Tools for Solving Production Planning Problems….Pages 317-346
From Spheres to Spheropolyhedra: Generalized Distinct Element Methodology and Algorithm Analysis….Pages 347-363
Graphic Submodular Function Minimization: A Graphic Approach and Applications….Pages 365-385
Matroids—the Engineers’ Revenge….Pages 387-398
On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming….Pages 399-428
Single-Sink Multicommodity Flow with Side Constraints….Pages 429-450
An Introduction to Network Flows over Time….Pages 451-482
Edge-Connectivity Augmentations of Graphs and Hypergraphs….Pages 483-521
Some Problems on Approximate Counting in Graphs and Matroids….Pages 523-544
Back Matter….Pages 545-562