399: Travelling Salesman Problem

Explain xkcd: It's 'cause you're dumb.
(Difference between revisions)
Jump to: navigation, search
(While big O uses mathematical notation, it's not math.)
(Transcript: A little cosmetic typesetting)
Line 17: Line 17:
 
:Brute-force solution:O(n!)
 
:Brute-force solution:O(n!)
 
:[The web continues in this one. A man with a hat and a case is drawing it]
 
:[The web continues in this one. A man with a hat and a case is drawing it]
:Dynamic programming algorithms: O(n^2 2^n)
+
:Dynamic programming algorithms: O(n<sup>2</sup>2<sup>n</sup>)
 
:[Another man, with a hat too, is at a computer, looking back over the chair]
 
:[Another man, with a hat too, is at a computer, looking back over the chair]
 
:Selling on eBay: O(1)
 
:Selling on eBay: O(1)

Revision as of 05:37, 15 November 2012

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 ...

Explanation

The Traveling salesman problem is a classic problem in computer science 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 returns to the origin city. A naive solution solves the problem in order of N! time (where N is the size of the list). The best algorithms can solve the problem in (N^2 * 2^N) order time, which is better but still extremely slow. The joke is that the computer salesman selling on eBay 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".

Also see previous strip 287: NP-Complete.

Transcript

[There is a linked black web, with a path in red]
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)
Computer salesman: Still working on your route?
Drawing salesman: Shut the hell up.
comment.png add a comment! ⋅ Icons-mini-action refresh blue.gif refresh comments!

Discussion

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. 130.160.145.185 23:07, 9 March 2013 (UTC)

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

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

"it is bitter news that in the forty years since Held and Karp no better guarantee [than n^2.2^n] has been found for the problem" [1]. So whereas linear programming techinques tend to be quicker than other algorithms, they have not been shown to be better than O(n^2.2^n).141.101.98.55 17:05, 17 August 2014 (UTC)

Doesn't someone at ebay still have to solve the TSP? I guess that's the entire point though. 141.101.85.223 08:48, 27 July 2014 (UTC)

No because you can send your sales information to all customers at once because they come to you, electronically. It takes no longer for you to be viewed by 100 people than by one person. Thus O(1). 141.101.98.55 17:05, 17 August 2014 (UTC)
I never used ebay so I don't know how it works and I'm probably missing something obvious. (Maybe it should be explained at the explanation?) If you wanted to personally sell about 17 items to 17 cities like the guy on the left, you have to visit each city by car or something. How does ebay visit the 17 cities to send the items?141.101.85.199 06:34, 19 August 2014 (UTC)
Personal tools
Namespaces

Variants
Actions
Navigation
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?