Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.
Résumé du séminaire du Mardi 26 Juin 2012
Approximation Hardness of Combinatorial Optimization Problems
par Janka Chlebikova (University of Portsmouth)
In the last years tight bounds on the efficient approximability for several optimization problems have been achieved using the Probabilistic Checkable Proof theory. However, the current state of the PCP technique hardly allows to obtain similar results for restricted instances of combinatorial optimization problems (e.g., in bounded degree graphs or in intersection graphs of some geometric objects). In this talk we present some techniques which were used to obtain currently the best inapproximability results for the Maximum Independent Set problem and other graph optimization problems in intersection graphs of 3-dimensional boxes.