The **Traveling Salesman Problem** is the following problem

**Domain:**\(T S P\)**Instance:**Integer \(n\ge 3\) and a symmetric matrix \(C=(c_{ij})\) with positive real numbers \(c_{ij} > 0\).**Question:**Which cyclic permutation \(\pi\) of the real numbers \(1\) to \(n\) minimizes the sum \(\sum_{i=1}^n c_{i\pi(i)}\)?

| | | | created: 2016-03-09 22:50:07 | modified: 2016-03-09 23:14:53 | by: *bookofproofs* | references: [1775]

(none)

[1775] **Lawler; Lenstra; Rinnooy Kan; Shmoys**: “The Traveling Salesman Problem”, Wiley-Interscience, 1985