Set TSP problem

In combinatorial optimization, the set TSP, also known as the, generalized TSP, group TSP, One-of-a-Set TSP, Multiple Choice TSP or Covering Salesman Problem, is a generalization of the Traveling salesman problem (TSP), whereby it is required to find a shortest tour in a graph which visits all specified disjoint subsets of the vertices of a graph. The ordinary TSP is a special case of the set TSP when all subsets to be visited are singletons. Therefore the set TSP is also NP-hard.

There is a direct reduction from set TSP to asymmetric TSP, and thus from set TSP to TSP. The idea is to arbitrarily assign a directed cycle to each set. The salesman, when visiting a vertex in some set, then walks around the cycle for free. To not use the cycle would ultimately be very costly.

References

'Bold text''''Bold text''''Bold text''''Bold text''''Bold text''''Bold text'

Bold text

• 
  Caption1
• 
  Caption2

• 
  Caption1
• 
  Caption2

• 
  Caption1
• 
  Caption2

• File:! Header text !! Header text !! Header text

</gallery> </gallery> </gallery> ''''''''''''''''