Abstract FR:

En general on etudie la complexite de l'approximation des problemes d'optimisation np-difficiles. Dans cette these 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 = co np. Nous avons consideres l'approximation de certains problemes de tfnp pour lesquels aucun algorithme polynomial n'est connu. Nous avons etudie le 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. Nous avons donne 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. Nous avons montre 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. Dans la suite nous nous sommes interesses au probleme du plus long cycle dans les graphes cubiques et hamiltoniens. Smith a montre que de tels graphes ont au moins deux cycles hamiltoniens. Nous avons etudie la complexite de l'approximation de ce probleme ou une solution possible est un deuxieme cycle. Nous montrons qu'il existe un schema d'approximation en temps polynomial efficace pour ce probleme. Trouver un cycle hamiltonien dans ces graphes est un probleme np-difficile. Nous prouvons 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.