1
$\begingroup$

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

  1. Can this be reduced to the original TSP?
  2. Is there any reference which deals with k-fold TSP? What is the name of this problem in the literature?
  3. Any heuristics/approximation algorithms?
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.