1
$\begingroup$

I am looking at a variant of TSP in which rather than visiting every node, there is a given collection of (possibly overlapping) subset, and the salesman must pass through one node from each subset.

Concretely, I have a graph with vertices $V$ and a family of subsets $S = \{S_1, S_2, ..., S_n \}$. I'm looking for a simple path $\{(v_1, v_2), (v_2, v_3), ..., (v_{m}, v_{1})\}$ such that for all $S_i$, there is a $k$ such that $v_k \in S_i$.

I'm interested in approximation algorithms, and heuristics for computing lower bounds for partial solutions for use in a branch and bound computation. Has this problem been studied elsewhere? If it helps, the problem is metric and the graph is complete.

$\endgroup$
1
  • $\begingroup$ The closest thing I've found so far is this paper, but it's still quite a bit different from this problem. $\endgroup$ Oct 22 at 4:41
1
$\begingroup$

The problem is known as the Generalized TSP problem.

$\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.