Combinatorial Optimization and Theoretical Computer Science ：Interfaces and Perspectives

Publication subTitle ：Interfaces and Perspectives

Author： Vangelis Th. Paschos  

Publisher： John Wiley & Sons Inc‎

Publication year： 2010

E-ISBN: 9780470393673

P-ISBN(Hardback):  9781848210219

Subject： TP301.6 algorithm theory

Language： ENG

Access to resources Favorite

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

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

Contents

pp.：  1 – 7

Preface

pp.：  7 – 17

Chapter 1. The Complexity of Single Machine Scheduling Problems under Scenario-based Uncertainty

pp.：  17 – 25

Chapter 2. Approximation of Multi-criteria Min and Max TSP(1, 2)

pp.：  25 – 39

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

Index

pp.：  509 – 513

LastPages

pp.：  513 – 518

The users who browse this book also browse


No browse record.