0399: "Travelling Salesman Problem"
Moderators: Moderators General, Prelates, Magistrates
0399: "Travelling Salesman Problem"
Alttext: What's the complexity class of the best linear programming cuttingplane techniques? I couldn't find it anywhere. Man, the Garfield guy doesn't have these problems ...
Link: http://xkcd.com/399/
My first reaction to this comic was "WHOA! Black hat dude has a brown hat now!". Then I read the comic and lol'd.
Re: "Travelling Salesman Problem" Discussion
While "traveling" and "travelling" are technically both correct spellings, I believe that "traveling" is more correct (and similarly, labeling, canceling, etc.).
[Edit] So after further research, it looks like "traveling" is considered the American spelling and "travelling" the British spelling [/Edit]
[Edit] So after further research, it looks like "traveling" is considered the American spelling and "travelling" the British spelling [/Edit]
Re: "Travelling Salesman Problem" Discussion
AlphaPyro wrote:While "traveling" and "travelling" are technically both correct spellings, I believe that "traveling" is more correct (and similarly, labeling, canceling, etc.).
[Edit] So after further research, it looks like "traveling" is considered the American spelling and "travelling" the British spelling [/Edit]
Dang, I was about to say the part about US vs UK, but you edited it too fast!
"Duct tape is like the Force. It has a light side, a dark side, and it holds the universe together." Carl Zwanzig
Re: "Travelling Salesman Problem" Discussion
Is that supposed to be 0*n! and 0*n^{2}*2^{n}? Wouldn't they both wind up being zero, like anything multiplied by zero would?
Re: "Travelling Salesman Problem" Discussion
AlphaPyro wrote:While "traveling" and "travelling" are technically both correct spellings, I believe that "traveling" is more correct (and similarly, labeling, canceling, etc.).
[Edit] So after further research, it looks like "traveling" is considered the American spelling and "travelling" the British spelling [/Edit]
This pedantry is disgusting.
As for the comic, can't believe I didn't think of eBay as the solution to the NPHard Trave[lll]ing salesman problem...so obvious.
Re: "Travelling Salesman Problem" Discussion
toysbfun wrote:Is that supposed to be 0*n! and 0*n^{2}*2^{n}? Wouldn't they both wind up being zero, like anything multiplied by zero would?
http://en.wikipedia.org/wiki/Big_O_notation
EDIT: My first ninja!
Last edited by jmorgan3 on Fri Mar 21, 2008 4:40 am UTC, edited 1 time in total.
This signature is Y2K compliant.
Last updated 6/29/108
Last updated 6/29/108
Re: "Travelling Salesman Problem" Discussion
If I recall correctly, a Bellman equation could be used here (right?). I've only had a minor brush with dynamic programming, but already I can say that eBay is far easier.
Except, of course, for selling babies. No one wants to pay shipping cost for those.
Except, of course, for selling babies. No one wants to pay shipping cost for those.
多么现在棕色母牛?
Re: "Travelling Salesman Problem" Discussion
toysbfun wrote:Is that supposed to be 0*n! and 0*n^{2}*2^{n}? Wouldn't they both wind up being zero, like anything multiplied by zero would?
Nope. It's BigO notation, which in computer science is used to measure the runtime of an algorithm. See: Wikipedia.
Edit: Ninja'd.
As for the comic, can't believe I didn't think of eBay as the solution to the NPHard Travell?ing salesman problem...so obvious.
Fix'd.
Re: "Travelling Salesman Problem" Discussion
and you have to watch out for when you get bobcats in the mail
Re: "Travelling Salesman Problem" Discussion
jmorgan3 wrote:toysbfun wrote:Is that supposed to be 0*n! and 0*n^{2}*2^{n}? Wouldn't they both wind up being zero, like anything multiplied by zero would?
http://en.wikipedia.org/wiki/Big_O_notation
Ah. Thanks.
Re: "Travelling Salesman Problem" Discussion
aeflash wrote:This pedantry is disgusting.
Actually, being a current computer science student, I've been dealing with Big O Notation pretty much every day, so the pedantry is oddly refreshing.
"Duct tape is like the Force. It has a light side, a dark side, and it holds the universe together." Carl Zwanzig
Re: "Travelling Salesman Problem" Discussion
Big O notation, because despite having 26 english letters, 24 greek letters, and the ability to make up symbols, we STILL choose the one letter easiest confused with a zero
Re: "Travelling Salesman Problem" Discussion
HAH! This comic makes sitting through those goddamn algorithms classes all worthwhile
 aleflamedyud
 wants your cookies
 Posts: 3307
 Joined: Tue Oct 09, 2007 7:50 pm UTC
 Location: The Central Bureaucracy
Re: "Travelling Salesman Problem" Discussion
And the comic goes straight back into the wide realm of Funny.
"With kindness comes naïveté. Courage becomes foolhardiness. And dedication has no reward. If you can't accept any of that, you are not fit to be a graduate student."
Re: "Travelling Salesman Problem" Discussion
Kalos wrote:Big O notation, because despite having 26 english letters, 24 greek letters, and the ability to make up symbols, we STILL choose the one letter easiest confused with a zero
If its suits you, Big Theta and Big Omega wouldn't mind some lovin'
Re: "Travelling Salesman Problem" Discussion
Is this the classhole with a new hat, or some other dude?
Re: "Travelling Salesman Problem" Discussion
After all this time, I still don't understand, P, NP, and NPcomplete, except that I know NPcomplete is hard/impossible. Maybe because I still don't get polynomial time? What the hell. Is big O notation about finding the solution or the optimum time it takes to find a solution? And what, in seconds? Gah this is confusing.
Re: "Travelling Salesman Problem" Discussion
thebandit wrote:Is this the classhole with a new hat, or some other dude?
I'm putting my money on different guys.
Re: "Travelling Salesman Problem" Discussion
That is a travelingsalesmanhat, and the guys wearing it are traveling salesmen. They are not classholes of any kind (although they may come perilously close to assholeland from time to time).thebandit wrote:Is this the classhole with a new hat, or some other dude?
(Look what I did there )
Also, much agreement about the silliness of the bigO notation. These nice letters could use some lovin', don't you think?
Re: "Travelling Salesman Problem" Discussion
Ashbash wrote:After all this time, I still don't understand, P, NP, and NPcomplete, except that I know NPcomplete is hard/impossible. Maybe because I still don't get polynomial time? What the hell. Is big O notation about finding the solution or the optimum time it takes to find a solution? And what, in seconds? Gah this is confusing.
Neither. Big O notation is about how the time to process a function changes as the problem gets bigger. If a program is O(n), then it scales linearly  you double the size of the problem, you double the time it takes. If it's O(n^{2}), then if you double the size of the problem, you quadruple the time it takes, etc.
Re: "Travelling Salesman Problem" Discussion
The rollover reminded me of http://en.wikipedia.org/wiki/Spaghetti_sort, the O(n) sort algorithm.
Last edited by ddunham on Fri Mar 21, 2008 5:26 am UTC, edited 1 time in total.

 Posts: 5
 Joined: Mon Nov 19, 2007 5:08 am UTC
Re: "Travelling Salesman Problem" Discussion
As soon as I saw the title of this comic in my RSS feed, I knew I was gonna be happy... and sure enough, I was not disappointed. This comic singlehandedly makes last semester (and my algorithm analysis class in particular) worthwhile.
 sqrt(1)<3pi
 Posts: 28
 Joined: Mon Feb 04, 2008 9:49 pm UTC
Re: "Travelling Salesman Problem" Discussion
Kalos wrote:Big O notation, because despite having 26 english letters, 24 greek letters, and the ability to make up symbols, we STILL choose the one letter easiest confused with a zero
But if we chose something else we could possibly lose all the fun sexual innuendos! As lonely(or immature) computer scientists supressed giggles are necessary!!
Also, i was almost expecting the alttext to include: "For everything else, there's eBay"
This comic is so full of win
public static String reCurse()
{
``````return "Damnit!" +reCurse();
}
[the 4th root of n]*([the previous number  1] to the 4th)(the product of the 2 numbers in brackets)=the answer to Life the Universe and Everything, where n is the page of my post in the intro thread
{
``````return "Damnit!" +reCurse();
}
[the 4th root of n]*([the previous number  1] to the 4th)(the product of the 2 numbers in brackets)=the answer to Life the Universe and Everything, where n is the page of my post in the intro thread
Re: "Travelling Salesman Problem" Discussion
Kalos wrote:Big O notation, because despite having 26 english letters, 24 greek letters, and the ability to make up symbols, we STILL choose the one letter easiest confused with a zero
Don't forget the Hebrew alphabet. We use that from time to time... though really only א (Aleph) as far as I know. (Do any of the others get used? What does שּ (Shin) stand for?)
ddunham wrote:The rollover reminded me of http://en.wikipedia.org/wiki/Spaghetti_sort, the O(n) sort algorithm.
I like spaghetti. I like sorting. I now love Spaghetti Sort. I've never seen that before, but it is the best kind of computer humor: totally correct, totally useless, utterly absurd!

 Posts: 163
 Joined: Wed Aug 22, 2007 6:17 am UTC
Re: "Travelling Salesman Problem" Discussion
And now, Traveling Salesman becomes clear: let [the postal service, UPS, FedEx, other carrier] do the traveling for you and let someone else take care of a far simpler problem. It's a vaguely recursive solution that makes everything much simpler.
As for underused symbols, I nominate 'n̈'. As in "Spın̈al Tap". It's not even in Unicode, which disappoints me greatlyyou've got to merge the unicode for 'n' and the one for the diaeresis.
As for underused symbols, I nominate 'n̈'. As in "Spın̈al Tap". It's not even in Unicode, which disappoints me greatlyyou've got to merge the unicode for 'n' and the one for the diaeresis.
While I clicked my fav'rite bookmark, suddenly there came a warning,
And my heart was filled with mournng, mourning for my dear amour.
"'Tis not possible!" I uttered, "Give me back my free hardcore!"
Quoth the server: 404.
And my heart was filled with mournng, mourning for my dear amour.
"'Tis not possible!" I uttered, "Give me back my free hardcore!"
Quoth the server: 404.
Re: "Travelling Salesman Problem" Discussion
photosinensis wrote:And now, Traveling Salesman becomes clear: let [the postal service, UPS, FedEx, other carrier] do the traveling for you and let someone else take care of a far simpler problem. It's a vaguely recursive solution that makes everything much simpler.
As for underused symbols, I nominate 'n̈'. As in "Spın̈al Tap". It's not even in Unicode, which disappoints me greatlyyou've got to merge the unicode for 'n' and the one for the diaeresis.
the second derivative of n with respect to time?
EDIT: I can't believe I just made that observation ... the pure mathematician inside of me is dying.
http://www.cdbaby.com/cd/mudge < buy my CD (Now back in stock!)

 Posts: 30
 Joined: Mon Feb 25, 2008 5:08 am UTC
Re: "Travelling Salesman Problem" Discussion
Kalos wrote:Big O notation, because despite having 26 english letters, 24 greek letters, and the ability to make up symbols, we STILL choose the one letter easiest confused with a zero
I believe 'O' (or 'o') stands for 'order of ', as in O(n) is of the order of n and so on.
Kthxbye
 faunablues
 Posts: 95
 Joined: Wed Feb 27, 2008 3:14 am UTC
Re: "Travelling Salesman Problem" Discussion
Classhole or no classhole, that hat looks like crap. I shall dub it CrapHat.

 Posts: 1
 Joined: Fri Mar 21, 2008 6:11 am UTC
Re: "Travelling Salesman Problem" Discussion
It is, indeed, surprisingly difficult to find an asymptotic running time for any of the chvatal et al. integer programming cutting plane solutions...
I offer up instead a $O(1.6423^n)$ solution to 3SAT...hey it's within a polynomial factor, right?
New upper bound for the #3SAT problem. Konstantin Kutzkov.
Information Processing Letters, Volume 105, Issue 1, 31 December 2007, Pages 15
I offer up instead a $O(1.6423^n)$ solution to 3SAT...hey it's within a polynomial factor, right?
New upper bound for the #3SAT problem. Konstantin Kutzkov.
Information Processing Letters, Volume 105, Issue 1, 31 December 2007, Pages 15

 Posts: 3
 Joined: Fri Mar 21, 2008 6:24 am UTC
Re: "Travelling Salesman Problem" Discussion
Holy crap it's a map of the United States. It took me forever to get that.
I think the fever is really starting to affect (or, if you're XKCD, effect) my mental capacity.
I think the fever is really starting to affect (or, if you're XKCD, effect) my mental capacity.

 Posts: 2
 Joined: Fri Mar 21, 2008 6:19 am UTC
Re: "Travelling Salesman Problem" Discussion
geirskogul wrote:Holy crap it's a map of the United States. It took me forever to get that.
I think the fever is really starting to affect (or, if you're XKCD, effect) my mental capacity.
Wow, even I didn't notice that!
But how will the auction be held? Thus ebay support reverse auctions?

 Posts: 51
 Joined: Mon Sep 10, 2007 4:43 am UTC
Re: "Travelling Salesman Problem" Discussion
I wish this comic went up last week, I could have shown it to my Algorithms professor, but I just finished that class.

 Posts: 1
 Joined: Fri Mar 21, 2008 6:59 am UTC
Re: "Travelling Salesman Problem" Discussion
Paiev wrote:Alttext: What's the complexity class of the best linear programming cuttingplane techniques? I couldn't find it anywhere. Man, the Garfield guy doesn't have these problems ...
Ummm, that Garfield guy has plenty of his own problems. Have you ever read Garfield strips while imagining that Garfield is a cat that can't talk back to Jon? Jon Arbuckle is clinically depressed, not to mention stark raving mad.
http://garfieldminusgarfield.tumblr.com/
Re: "Travelling Salesman Problem" Discussion
And to think I used to be an antitechnology romantic. The internet is my favorite thing ever.
Raise up the torch and light the way.
Re: "Travelling Salesman Problem" Discussion
ddunham wrote:The rollover reminded me of http://en.wikipedia.org/wiki/Spaghetti_sort, the O(n) sort algorithm.
It is wrong to measure the space complexity (as according to the wikipedia article) as O(n) in units of rods. Each rod is length m. The space complexity is clearly O(nm). However, the input takes at most n log m bits to write down. This makes the space complexity exponential in the size of the input.

 Posts: 3
 Joined: Sat Dec 29, 2007 7:33 pm UTC
Re: "Travelling Salesman Problem" Discussion
Ashbash wrote:After all this time, I still don't understand, P, NP, and NPcomplete, except that I know NPcomplete is hard/impossible. Maybe because I still don't get polynomial time? What the hell. Is big O notation about finding the solution or the optimum time it takes to find a solution? And what, in seconds? Gah this is confusing.
Big O notation tells you about how algorithms scale relative to input size. Generally big O notation is used to mean the time "complexity" (time scaling) of algorithms relative to some measure of input size. Sorting a list is a common example. Sorting a list typically scales proportionately to the number of elements, n, in the list. Some simple sorting algorithms are O(n^2), which means they take 4 times longer to sort a list twice as long, you can see how inefficient that kind of algorithm becomes when you start to increase the input size a lot. More efficient sorting algorithms are O(n * log(n)), which means they scale relative to the product of the input size and the log of the input size. Since the logarithmic function grows very slowly this is vastly better than O(n^2). You can see, with an O(n^2) algorithm it takes some constant factor times a million times as long to sort a list 1,000 times longer, whereas with with an O(n*log(n)) algorithm it would take only some constant factor times about 7,000x as long with the same relative growth of input size. Add more zeroes and the difference becomes even more dramatic. Big O notation is extremely useful because it only describes the scaling characteristics of the algorithm, it doesn't describe the constants involved which vary by implementation, hardware, etc, so it's a measure which is independent of language, hardware, operating system, etc. Often times, improving the performance of a function comes down to twerking those constants (making inner loops faster, slimming down code so it fits in the cache, reducing highcost operations like I/O and memory access, etc.) but in some cases you may need to switch to an algorithm that has better scaling characteristics, which is where big O notation and computer science come into play.
There are a wide variety of problems in computing which have been proven to be solvable using algorithms which scale polynomially. These could still be horribly poorly scaling algorithms such as O(n^100) or such, but they still are bounded by polynomial functions. All such problems are grouped in the "P" complexity class.
The "NP" (nondeterministic polynomial time) complexity class includes everything inside the P complexity class as well as any problems for which checking if a given solution is correct is a P complexity problem (i.e. if the solution can be checked with polynomial time complexity algorithms).
A particular problem is in "NPComplete" if it's in NP and if every other problem in NP is equivalent in some way to a variant of it. Currently we do not know whether or not P and NP are actually different sets or if P actually equals NP and we just haven't found the right solutions to all the NP problems yet. NPComplete is an important set of problems which help explore that question.

 Posts: 28
 Joined: Wed Mar 28, 2007 9:58 am UTC
 Contact:
Re: "Travelling Salesman Problem" Discussion
Isn't there $1,000,000 set aside for the person to figure out an algorithm to find the shortest distance?
I've actually taken a stab or two at figuring that out. I suck at the higher maths, but am good with patterns. However, while there's a million bucks attached to it, I'd say it's at least 5 million worth of damned difficult.
I've actually taken a stab or two at figuring that out. I suck at the higher maths, but am good with patterns. However, while there's a million bucks attached to it, I'd say it's at least 5 million worth of damned difficult.
Well I thought it was funny.

 Posts: 57
 Joined: Sat Nov 10, 2007 9:56 am UTC
 Contact:
Re: "Travelling Salesman Problem" Discussion
WHOA GUYS
there appears to be a vertex of very high degree in between the first and second panels, located in what would seem to be the midwest? What might this indicate! PERHAPS it is to be the next point of a reallife XKCD meeting?!
there appears to be a vertex of very high degree in between the first and second panels, located in what would seem to be the midwest? What might this indicate! PERHAPS it is to be the next point of a reallife XKCD meeting?!

 Posts: 28
 Joined: Wed Mar 28, 2007 9:58 am UTC
 Contact:
Re: "Travelling Salesman Problem" Discussion
All I know is that Detroit isn't on the map.
No salesman in his right mind would go to Detroit anyway. His mugger would make fun of his hat.
No salesman in his right mind would go to Detroit anyway. His mugger would make fun of his hat.
Well I thought it was funny.
Return to “Individual XKCD Comic Threads”
Who is online
Users browsing this forum: Google Feedfetcher, IMSoP and 87 guests