Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives (Google eBook)

Front Cover
Vangelis Th. Paschos
John Wiley & Sons, Jan 5, 2010 - Technology & Engineering - 544 pages
0 Reviews
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.
  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Preface
15
Chapter 1 The Complexity of Single Machine Scheduling Problems under Scenariobased Uncertainty
23
Chapter 2 Approximation of Multicriteria Min and Max TSP1 2
37
Chapter 3 Online Models for Setcovering The Flaw of Greediness
71
Chapter 4 Comparison of Expressiveness for Timed Automata and Time Petri Nets
93
Chapter 5 A Maximum Node Clustering Problem
145
Chapter 6 The Patrolling Problem Theoretical and Experimental Results
161
Chapter 7 Restricted Classes of Utility Functions for Simple Negotiation Schemes Sufficiency Necessity and Maximality
175
Chapter 12 An Extensive Comparison of 01 Linear Programs for the Daily Satellite Mission Planning
319
Chapter 13 DantzigWolfe Decomposition for Linearly Constrained Stable Set Problem
329
Chapter 14 Algorithmic Games
339
Chapter 15 Flows
373
Chapter 16 The Complexity of the Exact Weighted Independent Set Problem
393
Chapter 17 The Labeled Perfect Matching in Bipartite Graphs Complexity and inApproximability
433
Chapter 18 Complexity and Approximation Results for Boundedsize Paths Packing Problems
455
Chapter 19 An Upper Bound for the Integer Quadratic Multiknapsack Problem
495

Chapter 8 Worstcase Complexity of Exact Algorithms for NPhard Problems
203
Chapter 9 The Online Track Assignment Problem
241
Chapter 10 Complexity and Approximation Results for the Min Weighted Node Coloring Problem
259
Chapter 11 Weighted Edge Coloring
291
List of Authors
507
Index
511
Copyright

Common terms and phrases

About the author (2010)

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

Bibliographic information