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:
Added Corporate 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 |