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 9 Février 1999

Sur l'approximation de fonctions totales de NP

par Cristina Bazgan (LRI, Orsay)

En general on etudie la complexite de l'approximation des problemes d'optimisation NP-difficiles. Nous nous sommes particulierement interesses aux problemes de la classe TFNP definie par Meggido et Papadimitriou qui contient des problemes dont chaque instance a une solution. Ces problemes ne peuvent pas etre FNP-difficiles sauf si NP=coNP. Nous avons considere l'approximation de certains problemes de TFNP pour lesquels aucun algorithme polynomial n'est connu.

Je parlerai du probleme de trouver deux sous-ensembles disjoints et non vides d'un ensemble de n entiers positifs tels que les sommes des entiers des deux sous-ensembles soient les plus proches possibles. Ce probleme a une variante totale interessante, pour laquelle il n'y a pas d'algorithme polynomial connu, quand la somme des n entiers est au plus 2^n-1. Je presenterai un schema d'approximation en temps completement polynomial pour la version du probleme ou la valeur d'une solution est le rapport entre les sommes d'entiers dans les deux sous-ensembles. Je montrerai aussi que la variante totale precedente est plus facile a approcher que le probleme general en definissant une autre version du probleme ou la valeur d'une solution est la difference entre les sommes des entiers des deux sous-ensembles.

Je parlerai aussi du probleme du plus long cycle dans les graphes cubiques et Hamiltoniens. Smith a montre que de tels graphes ont au moins deux cycles Hamiltoniens. Je montrerai qu'il existe un schema d'approximation en temps polynomial efficace pour le probleme qui consiste a trouver un deuxieme cycle Hamiltonien dans un graphe cubique et Hamiltonien. Trouver un cycle Hamiltonien dans ces graphes est un probleme NP-difficile. Je montrerai que le probleme du plus long cycle n'est pas approximable a une constante pres dans les graphes cubiques et Hamiltoniens a moins que P=NP.

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