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.

Improve this question
$\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$
    – Davis Yoshida
    Commented Oct 22, 2021 at 4:41

1 Answer 1

Reset to default
1
$\begingroup$

The problem is known as the Generalized TSP problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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