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.
Famous quotes containing the words set and/or problem:
“Stripped of the cunning artifices of the tailor, and standing forth in the garb of Eden,what a sorry set of round-shouldered, spindle-shanked, crane-necked varlets would civilized men appear!”
—Herman Melville (18191891)
“I tell you, sir, the only safeguard of order and discipline in the modern world is a standardized worker with interchangeable parts. That would solve the entire problem of management.”
—Jean Giraudoux (18821944)