Show that bringing together operational research and theoretical computer science can yield useful results for a range of applications. This book demonstrates the quality and range of research conducted by LAMSADE in these areas. It offers an overview of combinatorial optimization and theoretical computer science.

This title has two main objectives in mind: to show that bringing together operational research and theoretical computer science can yield useful results for a range of applications, and to demonstrate the quality and range of research conducted by 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.

• 1. The Complexity of Single Machine Scheduling Problems under Scenario-based Uncertainty, M. A. Aloulou, F. Della Croce.2. Approximation of Multi-criteria Min and Max TSP(1, 2), E. Angel, E. Bampis, L. Gourves, J. Monnot.3. Online Models for Set-covering: the Flaw ofGreediness, G. Ausiello, A. Giannakos, V. Th. Paschos.4. Comparison of Expressiveness for TimedAutomata and Time Petri Nets, B. Berard, 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 andExperimental 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 forNP-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, Cecile Murat.16. The Complexity of the Exact Weighted Independent Set Problem, Martin Milanic, Jerome Monnot.17. The Labeled Perfect Matching in Bipartite Graphs: Complexity and (in)Approximability, Jerome Monnot.18. Complexity and Approximation Results for Bounded-size Path Packing Problems, Jerome Monnot, Sophie Toulouse.19. An Upper Bound for the Integer Quadratic Multi-knapsack Problem, Dominique Quadri, Eric Soutif, Pierre Tolla.