◀ ▲ ▶Branches / Theoretical-computer-science / Complexity-theory / Problem: TSP - The Traveling Salesman Problem

Problem: TSP - The Traveling Salesman Problem

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)}\)?

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Lawler; Lenstra; Rinnooy Kan; Shmoys: "The Traveling Salesman Problem", Wiley-Interscience, 1985