Combinatorial Optimization -- Eureka, You Shrink!: Papers Dedicated to Jack Edmonds. 5th International Workshop, Aussois, France, March 5-9, 2001, Revised Papers

by Michael Jïnger (Editor), Gerhard Reinelt (Editor), Giovanni Rinaldi (Editor)

Overview

This book is dedicated to Jack Edmonds in appreciation of his ground breaking work that laid the foundations for a broad variety of subsequent results achieved in combinatorial optimization. The main part consists of 13 revised full papers on current topics in combinatorial optimization, presented at Aussois 2001, the Fifth Aussois Workshop on Combinatorial Optimization, March 5-9, 2001, and dedicated to Jack Edmonds. Additional highlights in this book are an account of an Aussois 2001 special session dedicated to Jack Edmonds including a speech given by William R. Pulleyblank as well as newly typeset versions of three up-to-now hardly accessible classical papers: - Submodular Functions, Matroids, and Certain Polyhedra
by Jack Edmonds - Matching: A Well-Solved Class of Integer Linear Programs
by Jack Edmonds and Ellis L. Johnson - Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
by Jack Edmonds and Richard M. Karp.

Product Details

ISBN-13:	9783540005803
Publisher:	Springer Berlin Heidelberg
Publication date:	04/28/2003
Series:	Lecture Notes in Computer Science , #2570
Edition description:	2003
Pages:	214
Product dimensions:	6.10(w) x 9.25(h) x 0.02(d)

Table of Contents

“Eureka — You Skrink!”.- “Eureka — You Shrink!”.- Submodular Functions, Matroids, and Certain Polyhedra.- Matching: A Well-Solved Class of Integer Linear Programs.- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.- Connected Matchings.- Hajós’ Construction and Polytopes.- Algorithmic Characterization of Bipartite b-Matching and Matroid Intersection.- Solving Real-World ATSP Instances by Branch-and-Cut.- The Bundle Method for Hard Combinatorial Optimization Problems.- The One-Commodity Pickup-and-Delivery Travelling Salesman Problem.- Reconstructing a Simple Polytope from Its Graph.- An Augment-and-Branch-and-Cut Framework for Mixed 0-1 Programming.- A Procedure of Facet Composition for the Symmetric Traveling Salesman Polytope.- Constructing New Facets of the Consecutive Ones Polytope.- A Simplex-Based Algorithm for 0-1 Mixed Integer Programming.- Mixed-Integer Value Functions in Shastic Programming.- Exact Algorithms for NP-Hard Problems: A Survey.