Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr