## Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives (Google eBook)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

15 | |

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 |

### Common terms and phrases

adjacent agents algorithm allocation assigned to V1 assume automaton bicriteria bipartite graphs bisimilar bisimulation calculate chapter chordal graphs clique competitive ratio complexity Computer configuration consider constraints contains corresponding cyclic strategy decomposition deduce deﬁne defined denote due to Lemma edge coloring element EWIS problem exists Figure gadget given graph G Hence independent set inequality instance integer interval graphs LABELED linear MAX-CUT maximal maximum degree MEC problem minr modular Nash equilibrium NP-complete NP-hard obtain online algorithm oo oo oo opt(I optimal solution Pareto curve partition perfect graphs perfect matching permutation graphs Petri Nets planar planar graphs players polynomial Proof pseudo-polynomial QMKP radix tree reachable resource sequence solved stable set strongly NP-complete subgraph subset take vertex THEOREM tour transition tree upper bound utility functions V2 resp vertices WEIGHTED NODE COLORING widget