I'm interested in the following variant of Travelling Salesman Problem sometimes called Partial TSP. I'm particulary interested in the euclidian version :

Input : A set $\{x_1,\dots,x_n\}\subset \mathbb{R}^2$ of $n$ points in the plane, and an integer $k\le n$.

Output : A tour of $k$ points $x_{i_1},\dots, x_{i_k}$

Minimize : The length of the tour.

Is there any PTAS for this problem, or APX-hardness results ? Does Arora's technique applies on this case ?

  • $\begingroup$ In general, Partial TSP is as hard as TSP (since when $k = n$ you get TSP). $\endgroup$ – Juho Jun 10 '18 at 14:35
  • $\begingroup$ I'd rather say that Partial TSP is harder than TSP since it's a more general problem. I'd like to find a case where this problem is "striclty" harder $\endgroup$ – Mathieu Mari Jun 11 '18 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.