K-fold Traveling salesman problem - A variant of TSP Consider a weighted graph $K_n$ and where the weights between vertices $i,j$ is $w_{ij}$. Consider a path, $\sigma$, passing through each vertex only once. Here $\sigma_i$ is the vertex in the $(i\%n)^{th}$ step of the path. (For example, $\sigma_{n+1} = \sigma_1$)

Traveling salesman problem (TSP) minimizes the following objective : $$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}$$

A variant of TSP, 2-Fold TSP, will additionally consider the weights between the 1-skipped vertices on the path. The objective of a 2-Fold TSP is to minimize

$$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}+w_{\sigma_i,\sigma_{i+2}}$$

and similarly the objective of K-fold TSP is to minimize

$$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}+w_{\sigma_i,\sigma_{i+2}}+\cdots+w_{\sigma_i,\sigma_{i+k}}$$

Question


Can this be reduced to the original TSP?
Is there any reference which deals with k-fold TSP? What is the name of this problem in the literature?
Any heuristics/approximation algorithms?
There was a paper on the arxive last month, dealing with this generalization of the TSP:


  The multi-stripe travelling salesman problem
  Eranda Cela, Vladimir Deineko, Gerhard J. Woeginger
  (Submitted on 20 Sep 2016)
  https://arxiv.org/abs/1609.09796  


The problem does not seem to have a particular name in the literature.