Description
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.
Chapter
Chapter 3. Online Models for Set-covering: The Flaw of Greediness
pp.:
39 – 73
Chapter 4. Comparison of Expressiveness for Timed Automata and Time Petri Nets
pp.:
73 – 95
Chapter 5. A “Maximum Node Clustering” Problem
pp.:
95 – 147
Chapter 6. The Patrolling Problem: Theoretical and Experimental Results
pp.:
147 – 163
Chapter 7. Restricted Classes of Utility Functions for Simple Negotiation Schemes: Sufficiency, Necessity and Maximality
pp.:
163 – 177
Chapter 8. Worst-case Complexity of Exact Algorithms for NP-hard Problems
pp.:
177 – 205
Chapter 9. The Online Track Assignment Problem
pp.:
205 – 243
Chapter 10. Complexity and Approximation Results for the Min Weighted Node Coloring Problem
pp.:
243 – 261
Chapter 11. Weighted Edge Coloring
pp.:
261 – 293
Chapter 12. An Extensive Comparison of 0-1 Linear Programs for the Daily Satellite Mission Planning
pp.:
293 – 321
Chapter 13. Dantzig-Wolfe Decomposition for Linearly Constrained Stable Set Problem
pp.:
321 – 331
Chapter 14. Algorithmic Games
pp.:
331 – 341
Chapter 15. Flows!
pp.:
341 – 375
Chapter 16. The Complexity of the Exact Weighted Independent Set Problem
pp.:
375 – 395
Chapter 17. The Labeled Perfect Matching in Bipartite Graphs: Complexity and (in)Approximability
pp.:
395 – 435
Chapter 18. Complexity and Approximation Results for Bounded-size Paths Packing Problems
pp.:
435 – 457
Chapter 19. An Upper Bound for the Integer Quadratic Multi-knapsack Problem
pp.:
457 – 497
List of Authors
pp.:
497 – 509