Mitchell, Aurora have a PTAS for metric TSP that has a competitive factor something like O(1+1/c) and runtime O(N (logN)^O(c) ). For small factors, and c~=10 (Paper shows Amoeboid get about 90% of the best solution, apparently), I can see why it would look linear in the regime of N=[4,8].

I should mention, I don't think there's a working implementation of that PTAS however, and I only skimmed the article.

https://www.wolframalpha.com/input/?i=x*log(x)%5E2