The traveling-salesman problem

Improvement Table

Complexity Classes	Algorithm Paper Links	Lower Bounds Paper Links
Exp/Factorial	Held–Karp algorithm (1962) Christofides algorithm (1976) Lawler; E. L. (1985) (1985) TSPLIB 1991 (1991) Dantzig-Fulkerson-Johnson formulation (1977)
Polynomial > 3	Miller-Tucker-Zemlin formulation (1960) Johnson; D. S.; McGeoch; L. A. (1997) (1997)
Cubic	Gutina; Gregory; Yeob; Anders; Zverovich; Alexey (2002) (2002) Applegate et al. (2006) (2006)
Quadratic	Rosenkrantz; D. J.; Stearns; R. E.; Lewis; P. M. 1974 (1974) Lin–Kernighan (1981) Woeginger (2003) (2003)
nlogn
Linear
logn