# 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 16 Mars 1999

## par Vangelis Th. Paschos (Lamsade, Paris Dauphine)

We prove that both minimum and maximum traveling salesman problems can be approximately solving, in polynomial time, by a constant-ratio differential approximation algorithm. Based upon this result, we then improve the standard approximation ratio known for maximum traveling salesman with distances 1 and 2. Finally, we prove that, for any $\epsilon > 0$, it is \textbf{NP}-hard to approximate both problems within better than $4707/4708 + \epsilon$.

 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