[xkcd] Travelling Salesman Problem (21 Mar 2008)
[xkcd] Travelling Salesman Problem (21 Mar 2008)
Hover Text:
What's the complexity class of the best linear programming cutting-plane techniques? I couldn't find it anywhere. Man, the Garfield guy doesn't have these problems...
Transcript
[in a yellow box:]
[There is a linked black web, with a path in red; it appears to be a map of the United States.]
Brute-force solution:O(n!)
[The web continues in this one. A man with a brown hat and a case is drawing it.]
Dynamic programming algorithms: O(n22n)
[Another man, with a brown hat too, is at a computer, looking back over the chair.]
Selling on eBay: O(1)
eBay salesman: Still working on your route?
Drawing salesman: Shut the hell up.
You can say O(n^n) instead of O(n!) Its true and more dramatic!
Shouldn’t selling on eBay be O(n)? Since you have to sell each item individually. Still way better, but let’s be accurate here