Combinatorial Optimization and Theoretical Computer Science

Interfaces and Perspectives 30th Anniversary of the LAMSADE

ISBN: 9781848210219

Publication Date: January 2008   Hardback   520 pp.

195.00 USD

eBooks

Description

This book addresses two main objectives: to show that bringing together operational research and theoretical computer science can yield useful results for a range of applications, and secondarily to demonstrate the quality and range of research conducted by the LAMSADE in these areas. With this in mind, it offers a comprehensive overview of combinatorial optimization and theoretical computer science, featuring chapters written by a wide range of authors who are experts in their specific field.

Contents

1. The Complexity of Single Machine Scheduling Problems under Scenario-based Uncertainty, M. A. Aloulou, F. Della Croce.
2. Approximability of the Multi-criteria Min and Max TSP(1, 2), E. Angel, E. Bampis, L. Gourvès, J. Monnot.
3. Online Models for Set-covering: the Flaw of
Greediness, G. Ausiello, A. Giannakos, V. Th. Paschos.
4. Comparison of Expressiveness for Timed Automata and Time Petri Nets, B. Bérard, F. Cassez, S. Haddad, D. Lime, O. H. Roux.
5. A “Maximum Node Clustering” Problem,
G. Carello, F. Della Croce, A. Grosso, M. Locatelli.
6. The Patrolling Problem: Theoretical and Experimental Results,
Y. Chevaleyre.
7. Restricted Classes of Utility Functions for Simple Negotiation Schemes: Sufficiency, Necessity and Maximality,
Y. Chevaleyre, U. Endriss, N. Maudet.
8. Worst-case Complexity of Exact Algorithms for NP-hard Problems,
F. Della Croce, B. Escoffier, M. Kaminski, V. Th. Paschos.
9. The Online Track Assignment Problem,
M. Demange, G. Di Stefano, B. Leroy-Beaulieu.
10. Complexity and Approximation Results for the Min Weighted Node Coloring Problem, M. Demange et al.
11. Weighted Edge Coloring, M. Demange et al.
12. An Extensive Comparison of 0-1 Linear Programs for the Daily Satellite Mission Planning, Virginie Gabrel.
13. Dantzig-Wolfe Decomposition for Linearly Constrained Stable Set Problem, Virginie Gabrel.
14. Algorithmic Games, Aristotelis Giannakos et al.
15. Flows!, Michel Koskas, Cécile Murat.
16. The Complexity of the Exact Weighted Independent Set Problem, Martin Milanic, Jérôme Monnot.
17. The Labeled Perfect Matching in Bipartite Graphs: Complexity and (in) Approximability, Jérôme Monnot.
18. Bounded-size Path, Jérôme Monnot, Sophie Toulouse.
19. An Upper Bound for the Integer Quadratic Multi-knapsack Problem, Dominique Quadri, Eric Soutif, Pierre Tolla.

About the Authors

Vangelis Th. Paschos is Professor of Computer Science at the University of Paris-Dauphine and Chairman of the LAMSADE (Laboratory for the Modeling and the Analysis of Decision Aiding Systems). His research interests include complexity theory, the theory of the polynomial approximation of NP-hard problems, probabilistic combinatorial optimization and on-line computation. He is the author of more than a 100 research papers and is a member of the editorial board of several international scientific journals.

Downloads

Table of Contents - PDF File - 152 Kb

Preface - PDF File - 86 Kb