Traveling Salesman Problem

The input is an undirected graph G = (V, E) along with edge lengths l. The graph is complete.

Given a budget b > 0, find a tour that visits each vertex exactly once and has length ≤ b, or determine that no tour exists. Or… Find a tour that visits each vertex in G once and has minimum length.

There are two variants:

1. Optimization problem:
   1. Find a tour that visits each vertex in G exactly once and has minimum length
2. Search problem:
   1. Given a budget b>0, find a tour that visits each vertex exactly once and has length ≤ b or determine on such tour exists These two problems reduce to each other