The traveling-salesman problem
Revision as of 12:01, 10 October 2022 by Admin (talk | contribs) (Created page with "== Problem Description== == Bounds Chart == 350px == Step Chart == 350px == Improvement Table == {| class="wikitable" style="text-align:center;" width="100%" !width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links |- | rowspan="1" | Exp/Factorial | [https://www.jstor.org/stable/2098806 Held–Karp al...")
Problem Description
Bounds Chart
File:The traveling-salesman problemBoundsChart.png
Step Chart
File:The traveling-salesman problemStepChart.png
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | Held–Karp algorithm (1962) | |
| Polynomial > 3 | Miller-Tucker-Zemlin formulation (1960) | |
| Cubic | Gutina; Gregory; Yeob; Anders; Zverovich; Alexey (2002) (2002) | |
| Quadratic | Rosenkrantz; D. J.; Stearns; R. E.; Lewis; P. M. 1974 (1974) | |
| nlogn | ||
| Linear | ||
| logn |