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.