Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM TRAVELING SALESPERSON

• INSTANCE: Set C of m cities, distances $d(c_i,c_j)\in N$ for each pair of cities $c_i,c_j\in C$.

• SOLUTION: A tour of C, i.e., a permutation $\pi: [1..m]\rightarrow[1..m]$.

• MEASURE: The length of the tour, i.e., $d\left(\{c_{\pi(m)},c_{\pi(1)}\}\right)+\displaystyle\sum\limits_{i=1}^{m-1} d\left(\{c_{\pi(i)},c_{\pi(i+1)}\}\right)$.

  
  

• Bad News: NPO-complete [388].

• Comment: The corresponding maximization problem (finding the tour of maximum length) is approximable within 4/3 if the distance function is symmetric [434] (within $(33+\varepsilon )/25$ by a randomized algorithm [240]) and 63/38 if it is asymmetric [337].

• Garey and Johnson: ND22