Combinatorial optimization and theoretical computer science: interfaces and perspectives : 30th anniversary of the LAMSADE
Vangelis Th Paschos, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (France)
ISTE, 2008 - Computers - 515 pages
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.
The Complexity of Single Machine Scheduling Problems
Approximation of Multicriteria Min and Max TSP1 2
18 other sections not shown
Other editions - View all
adjacent agents allocation assigned to V2 assume automaton bicriteria bipartite graphs bisimilar bisimulation calculate chapter chordal graphs clique coloring problem competitive ratio complexity configuration consider constraints construction contains corresponding cyclic strategy decomposition deduce defined denote due to Lemma edge coloring element equivalent EWIS problem exists Figure gadget given graph G Hence independent set inequality input instance integer interval graphs knapsack problem Labeled linear matching problem MAX-CUT maximal maximum degree MEC problem modular Nash equilibrium NP-complete NP-hard obtain oo oo oo optimal solution Pareto curve partition perfect graphs perfect matching permutation permutation graphs Petri Nets planar planar graphs players polynomial Proof pseudo-polynomial QMKP radix tree reachable relation resource satisfies sequence solved stable set step strongly NP-complete subgraph subset take vertex Theorem tour transition tree upper bound utility functions V2 resp vertices WeIGHTeD nODe COLORInG widget