4 ms·
Amoeboid solves np complete problem in linear time
- deleted 8y ago[deleted]
- jvanderbot 8y agoMitchell, 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 https://www.wolframalpha.com/input/?i=x*log(x)%5E2