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

  1. Finally, we prove that, for any $\epsilon > 0$, it is \textbf{NP}-hard to approximate both problems within better than $4707/4708 + \epsilon$.