Vangelis Th. Paschos - Paradigms of Combinatorial Optimization

Paradigms of Combinatorial Optimization is the second volume of the Combinatorial Optimization series. It deals with advanced concepts as well as a series of problems, studies and research which have made, and continue to make, their mark on the evolution of this discipline. This work is divided into two parts:

: Paradigmatic Problems;

: New Approaches.

contains the following chapters:

Optimal Satisfiability by Cristina Bazgan;

Scheduling Problems by Philippe Chrtienne and Christophe Picouleau;

Location Problems by Aristotelis Giannakos;

MinMax Algorithms and Games by Michel Koskas;

Two-dimensional Bin Packing Problems by Andrea Lodi, Silvano Martello, Michele Monaci and Daniele Vigo;

The Maximum Cut Problem by Walid Ben-Ameur, Ali Ridha Mahjoub and Jos Neto;

The Traveling Salesman Problem and its Variations by Jrme Monnot and Sophie Toulouse;

01 Knapsack Problems by Grard Plateau and Anass Nagih;

Integer Quadratic Knapsack Problems by Dominique Quadri, Eric Soutif and Pierre Tolla;

Graph Coloring Problems by Dominique De Werra and Daniel Kobler.

All these chapters not only deal with the problems in question, but also highlight various tools and methods from combinatorial optimization and operations research. Obviously, this list is very limited and does not pretend to cover all the flagship problems in combinatorial optimization.

It is best to view the problems in this book as a sample that testifies to the richness of the themes and problems that can be tackled by combinatorial optimization, and of the tools developed by this discipline.

includes the following chapters:

Polynomial Approximation by Marc Demange and Vangelis Th. Paschos;

Approximation Preserving Reductions by Giorgio Ausiello and Vangelis Th. Paschos;

Inapproximability of Combinatorial Optimization Problems by Luca Trevisan;

Local Search: Complexity and Approximation by Eric Angel, Petros Christopoulos and Vassilis Zissimopoulos;

On-line Algorithms by Giorgio Ausiello and Luca Becchetti;

Polynomial Approximation for Multicriteria Combinatorial Optimization Problems by Eric Angel, Evripidis Bampis and Laurent Gourvs;

An Introduction to Inverse Combinatorial Problems by Marc Demange and Jrme Monnot;

Probabilistic Combinatorial Optimization by Ccile Murat and Vangelis Th. Paschos;

Robust Shortest Path Problems by Virginie Gabrel and Ccile Murat;

Algorithmic Games by Aristotelis Giannakos and Vangelis Th. Paschos.

The themes of this part are at the border between research operations and combinatorial optimization, theoretical computer science and discrete mathematics. Nevertheless, all these subjects have their rightful place in the vast scientific field that we call combinatorial optimization. They are developed, at least in part, at the heart of this discipline, fertilize it, widen its renown, and enrich its models.

For this volume, my thanks go firstly to the authors who have agreed to participate in the book. This work could never have come into being without the original proposal of Jean-Charles Pomerol, Vice President of the scientific committee at Hermes, and Sami Mnasc and Raphal Mnasc, the heads of publications at ISTE. I give my warmest thanks to them for their insistence and encouragement. It is a pleasure to work with them as well as with Rupert Heywood who has ingeniously translated this books material from the original French.

Vangelis Th. PASCHOS

June 2010