399: Travelling Salesman Problem

Explain xkcd: It's 'cause you're dumb.
Jump to: navigation, search
Travelling Salesman Problem
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...
Title 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...

[edit] Explanation

The Travelling salesman problem is a classic problem in computer science. An intuitive way of stating this problem is that given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and then returns to the origin city. A naive solution solves the problem in O(n!) time (where n is the size of the list), simply by checking all possible routes, and selecting the shortest one. A more efficient dynamic programming approach yields a solution in O(n22n) time. These times are given using Big O notation, which is commonly used in computer science to show the efficiency or complexity of a solution or algorithm.

The joke is that the salesman selling online (say on eBay, Amazon Marketplace, or other virtual marketplace) does not have to worry about this problem since he does not need to travel, to which the travelling salesman angrily responds "shut the hell up".

The title text wonders about the time complexity of the Cutting-plane method, which is sometimes used to solve optimization problems. The last sentence suggests the down side for Randall of writing comics about computer science; he sometimes encounters problems to which he cannot find the answer, whereas authors of simpler comics such as Garfield do not have this problem. This is also likely a reference to 78: Garfield, which parodies Garfield's simplicity.

This is so far the only comic featuring the Brown Hat character.

Also see previous strip 287: NP-Complete.

[edit] Transcript

[There is a linked black web, with a path in red; it may be a map of the USA.]
Brute-force solution:O(n!)
[The web continues in this one. A man with a hat and a case is drawing it.]
Dynamic programming algorithms: O(n22n)
[Another man, with a 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.
comment.png add a comment!


Does anyone remember if the Brown Hat appears in any other comics?

I'm not sure, so I created a category and page for him, let's see if that catches any others. --Jeff (talk) 22:04, 29 March 2013 (UTC)
According to the transcript we have two different Brown Hat Guys here. I'm working on this.--Dgbrt (talk) 21:49, 5 October 2013 (UTC)
I'm inclined to think that Brown Hat is specific to this comic, the brown hat being the 50's style homburg or fedora common to salesmen trying to look respectable... Randall likely added the hats to depict folks from a bygone era, (one of whom has caught up with the trend.) -- IronyChef (talk) 01:49, 10 January 2014 (UTC)

It's probably not in the least important, but the network appears to be a collection of key cities in the US arranged by geographical location. 23:07, 9 March 2013 (UTC)

added a better explanation of the title text. -- Nick,5 Oct 2013 (talk) (please sign your comments with ~~~~)

Has anyone answered the question in the title text? --Ricketybridge (talk) 23:55, 9 January 2014 (UTC)
Personal tools


It seems you are using noscript, which is stopping our project wonderful ads from working. Explain xkcd uses ads to pay for bandwidth, and we manually approve all our advertisers, and our ads are restricted to unobtrusive images and slow animated GIFs. If you found this site helpful, please consider whitelisting us.

Want to advertise with us, or donate to us with Paypal or Bitcoin?