Cover image for Combinatorial optimization and theorical computer science : interfaces and perspectives
Title:
Combinatorial optimization and theorical computer science : interfaces and perspectives
Publication Information:
London : Wiley-ISTE, 2008
Physical Description:
515 p. : ill. ; 24 cm.
ISBN:
9781848210219
Added Author:

Available:*

Library
Item Barcode
Call Number
Material Type
Item Category 1
Status
Searching...
30000010191325 QA402.5 C654 2008 Open Access Book Book
Searching...

On Order

Summary

Summary

This volume is dedicated to the theme "Combinatorial Optimization - Theoretical Computer Science: Interfaces and Perspectives" and has two main objectives: the first is to show that bringing together operational research and theoretical computer science can yield useful results for a range of applications, while the second is to demonstrate the quality and range of research conducted by the LAMSADE in these areas.


Author Notes

Vangelis Th. Paschos is a Professor of Computer Science at the University of Paris-Dauphine, France.


Table of Contents

Chapter 1 The Complexity of Single Machine Scheduling Problems under Scenario-based UncertaintyM. A. Aloulou and F. Della Croce
Chapter 2 (Non)-Approximability Results for the Multi-criteria Min and Max TSP(1, 2)E. Angel and E. Bampis and L. Gourv+s and J. Monnot
Chapter 3 Online Models for Set-covering: the Flaw of GreedinessG. Ausiello and A. Giannakos and V. Th. Paschos
Chapter 4 Comparison of Expressiveness for Timed Automata and Time Petri NetsB. B_rard and F. Cassez and S. Haddad and D. Lime and O. H. Roux
Chapter 5 A "Maximum Node Clustering" ProblemG. Carello and F. Della Croce and A. Grosso and M. Locatelli
Chapter 6 The Patrolling Problem: Theoretical and Experimental ResultsY. Chevaleyre
Chapter 7 Restricted Classes of Utility Functions for Simple Negotiation Schemes: Sufficiency, Necessity and MaximalityY. Chevaleyre and U. Endriss and N. Maudet
Chapter 8 Worst-case Complexity of Exact Algorithms for NP-hard ProblemsF. Della Croce and B. Escoffier and M. Kaminski and V. Th. Paschos
Chapter 9 The Online Track Assignment ProblemM. Demange and G. Di Stefano and B. Leroy-Beaulieu
Chapter 10 Complexity and Approximation Results for the Min Weighted Node Coloring ProblemM. Demange et al.
Chapter 11 Weighted Edge ColoringM. Demange et al.
Chapter 12 An Extensive Comparison of 0-1 Linear Programs for the Daily Satellite Mission PlanningVirginie Gabrel
Chapter 13 Dantzig-Wolfe Decomposition for Linearly Constrained Stable Set ProblemVirginie Gabrel
Chapter 14 Algorithmic GamesAristotelis Giannakos et al.
Chapter 15 Flows!Michel Koskas and C_cile Murat
Chapter 16 The Complexity of the Exact Weighted Independent Set ProblemMartin Milanic and J_rome Monnot
Chapter 17 The Labeled Perfect Matching in Bipartite Graphs: Complexity and (in) ApproximabilityJ_rome Monnot
Chapter 18 Complexity and Approximation Results for Bounded-size Paths Packing ProblemsJ_rome Monnot and Sophie Toulouse
Chapter 19 An Upper Bound for the Integer Quadratic Multi-knapsack ProblemDominique Quadri and Eric Soutif and Pierre Tolla
List of Authors
Index