0399: "Travelling Salesman Problem"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

Paiev
Posts: 51
Joined: Sat Nov 17, 2007 11:17 pm UTC

0399: "Travelling Salesman Problem"

Postby Paiev » Fri Mar 21, 2008 4:19 am UTC

Image

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

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.

AlphaPyro
Posts: 16
Joined: Mon May 21, 2007 4:18 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby AlphaPyro » Fri Mar 21, 2008 4:21 am UTC

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]

User avatar
1337geek
Posts: 551
Joined: Mon Oct 01, 2007 4:21 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby 1337geek » Fri Mar 21, 2008 4:24 am UTC

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

toysbfun
Posts: 171
Joined: Fri Apr 13, 2007 5:14 am UTC
Contact:

Re: "Travelling Salesman Problem" Discussion

Postby toysbfun » Fri Mar 21, 2008 4:31 am UTC

Is that supposed to be 0*n! and 0*n2*2n? Wouldn't they both wind up being zero, like anything multiplied by zero would?

User avatar
aeflash
Posts: 11
Joined: Wed Nov 14, 2007 7:20 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby aeflash » Fri Mar 21, 2008 4:32 am UTC

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 NP-Hard Trave[l|ll]ing salesman problem...so obvious.

User avatar
jmorgan3
Posts: 710
Joined: Sat Jan 26, 2008 12:22 am UTC
Location: Pasadena, CA

Re: "Travelling Salesman Problem" Discussion

Postby jmorgan3 » Fri Mar 21, 2008 4:34 am UTC

toysbfun wrote:Is that supposed to be 0*n! and 0*n2*2n? 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

User avatar
benjhuey
Posts: 3328
Joined: Sat Sep 08, 2007 2:35 am UTC
Location: A collection of rocks

Re: "Travelling Salesman Problem" Discussion

Postby benjhuey » Fri Mar 21, 2008 4:35 am UTC

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.
多么现在棕色母牛?

Paiev
Posts: 51
Joined: Sat Nov 17, 2007 11:17 pm UTC

Re: "Travelling Salesman Problem" Discussion

Postby Paiev » Fri Mar 21, 2008 4:36 am UTC

toysbfun wrote:Is that supposed to be 0*n! and 0*n2*2n? Wouldn't they both wind up being zero, like anything multiplied by zero would?


Nope. It's Big-O 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 NP-Hard Travell?ing salesman problem...so obvious.


Fix'd.

User avatar
4=5
Posts: 2073
Joined: Sat Apr 28, 2007 3:02 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby 4=5 » Fri Mar 21, 2008 4:37 am UTC

and you have to watch out for when you get bobcats in the mail

toysbfun
Posts: 171
Joined: Fri Apr 13, 2007 5:14 am UTC
Contact:

Re: "Travelling Salesman Problem" Discussion

Postby toysbfun » Fri Mar 21, 2008 4:38 am UTC

jmorgan3 wrote:
toysbfun wrote:Is that supposed to be 0*n! and 0*n2*2n? Wouldn't they both wind up being zero, like anything multiplied by zero would?


http://en.wikipedia.org/wiki/Big_O_notation


Ah. Thanks.

User avatar
1337geek
Posts: 551
Joined: Mon Oct 01, 2007 4:21 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby 1337geek » Fri Mar 21, 2008 4:41 am UTC

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

Kalos
Posts: 172
Joined: Thu Jan 31, 2008 6:45 pm UTC

Re: "Travelling Salesman Problem" Discussion

Postby Kalos » Fri Mar 21, 2008 4:49 am UTC

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

DSDM
Posts: 112
Joined: Fri Nov 02, 2007 5:14 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby DSDM » Fri Mar 21, 2008 4:53 am UTC

HAH! This comic makes sitting through those goddamn algorithms classes all worthwhile :lol:

User avatar
aleflamedyud
wants your cookies
Posts: 3307
Joined: Tue Oct 09, 2007 7:50 pm UTC
Location: The Central Bureaucracy

Re: "Travelling Salesman Problem" Discussion

Postby aleflamedyud » Fri Mar 21, 2008 4:58 am UTC

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

rascher
Posts: 12
Joined: Mon Aug 06, 2007 5:15 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby rascher » Fri Mar 21, 2008 4:59 am UTC

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'

thebandit
Posts: 91
Joined: Thu Jan 24, 2008 7:09 am UTC
Location: Sacramento

Re: "Travelling Salesman Problem" Discussion

Postby thebandit » Fri Mar 21, 2008 5:00 am UTC

Is this the classhole with a new hat, or some other dude?

Ashbash
Posts: 184
Joined: Thu Oct 11, 2007 5:46 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby Ashbash » Fri Mar 21, 2008 5:02 am UTC

After all this time, I still don't understand, P, NP, and NP-complete, except that I know NP-complete 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.

User avatar
Patashu
Answerful Bignitude
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:

Re: "Travelling Salesman Problem" Discussion

Postby Patashu » Fri Mar 21, 2008 5:03 am UTC

thebandit wrote:Is this the classhole with a new hat, or some other dude?

I'm putting my money on different guys.

++$_
Mo' Money
Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby ++$_ » Fri Mar 21, 2008 5:12 am UTC

thebandit wrote:Is this the classhole with a new hat, or some other dude?
That is a traveling-salesman-hat, and the guys wearing it are traveling salesmen. They are not classholes of any kind (although they may come perilously close to asshole-land from time to time).

(Look what I did there :))

Also, much agreement about the silliness of the big-O notation. These nice letters could use some lovin', don't you think?

Image

Shosei
Posts: 1
Joined: Fri Mar 21, 2008 5:08 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby Shosei » Fri Mar 21, 2008 5:13 am UTC

Ashbash wrote:After all this time, I still don't understand, P, NP, and NP-complete, except that I know NP-complete 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(n2), then if you double the size of the problem, you quadruple the time it takes, etc.

ddunham
Posts: 1
Joined: Fri Mar 21, 2008 5:21 am UTC
Location: Seattle

Re: "Travelling Salesman Problem" Discussion

Postby ddunham » Fri Mar 21, 2008 5:23 am UTC

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.

User avatar
aerojad
Wall O' AWESOME
Posts: 200
Joined: Wed Sep 26, 2007 8:54 am UTC
Location: Detroit, MI
Contact:

Re: "Travelling Salesman Problem" Discussion

Postby aerojad » Fri Mar 21, 2008 5:24 am UTC

fuck sales.

/got nothin'
Image

deathbybowtie
Posts: 5
Joined: Mon Nov 19, 2007 5:08 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby deathbybowtie » Fri Mar 21, 2008 5:34 am UTC

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.

User avatar
sqrt(-1)<3pi
Posts: 28
Joined: Mon Feb 04, 2008 9:49 pm UTC

Re: "Travelling Salesman Problem" Discussion

Postby sqrt(-1)<3pi » Fri Mar 21, 2008 5:46 am UTC

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 alt-text 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

zinder
Posts: 6
Joined: Sun Jan 13, 2008 8:26 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby zinder » Fri Mar 21, 2008 5:52 am UTC

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!

photosinensis
Posts: 163
Joined: Wed Aug 22, 2007 6:17 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby photosinensis » Fri Mar 21, 2008 5:55 am UTC

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 greatly--you'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.

User avatar
mudge
Posts: 292
Joined: Sun Sep 30, 2007 10:14 pm UTC
Location: Chicago
Contact:

Re: "Travelling Salesman Problem" Discussion

Postby mudge » Fri Mar 21, 2008 6:01 am UTC

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 greatly--you'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!)

marginally_stable
Posts: 30
Joined: Mon Feb 25, 2008 5:08 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby marginally_stable » Fri Mar 21, 2008 6:03 am UTC

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 :P

User avatar
faunablues
Posts: 95
Joined: Wed Feb 27, 2008 3:14 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby faunablues » Fri Mar 21, 2008 6:04 am UTC

Classhole or no classhole, that hat looks like crap. I shall dub it CrapHat.

excelsior84
Posts: 1
Joined: Fri Mar 21, 2008 6:11 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby excelsior84 » Fri Mar 21, 2008 6:21 am UTC

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 3-SAT...hey it's within a polynomial factor, right? :)

New upper bound for the #3-SAT problem. Konstantin Kutzkov.
Information Processing Letters, Volume 105, Issue 1, 31 December 2007, Pages 1-5

geirskogul
Posts: 3
Joined: Fri Mar 21, 2008 6:24 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby geirskogul » Fri Mar 21, 2008 6:25 am UTC

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.

rockhopper
Posts: 2
Joined: Fri Mar 21, 2008 6:19 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby rockhopper » Fri Mar 21, 2008 6:28 am UTC

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?

russianspy1234
Posts: 51
Joined: Mon Sep 10, 2007 4:43 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby russianspy1234 » Fri Mar 21, 2008 6:49 am UTC

I wish this comic went up last week, I could have shown it to my Algorithms professor, but I just finished that class.

crypticgeek
Posts: 1
Joined: Fri Mar 21, 2008 6:59 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby crypticgeek » Fri Mar 21, 2008 7:09 am UTC

Paiev wrote:Alt-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 ...


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/

User avatar
Quixotess
No. Cookies.
Posts: 3243
Joined: Mon May 28, 2007 7:26 am UTC
Contact:

Re: "Travelling Salesman Problem" Discussion

Postby Quixotess » Fri Mar 21, 2008 7:19 am UTC

And to think I used to be an anti-technology romantic. The internet is my favorite thing ever.
Raise up the torch and light the way.

glitter
Posts: 6
Joined: Sat Oct 28, 2006 2:27 am UTC

Re: "Travelling Salesman Problem" Discussion

Postby glitter » Fri Mar 21, 2008 9:08 am UTC

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.

rocketsocks
Posts: 3
Joined: Sat Dec 29, 2007 7:33 pm UTC

Re: "Travelling Salesman Problem" Discussion

Postby rocketsocks » Fri Mar 21, 2008 9:36 am UTC

Ashbash wrote:After all this time, I still don't understand, P, NP, and NP-complete, except that I know NP-complete 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 high-cost 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" (non-deterministic 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 "NP-Complete" 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. NP-Complete is an important set of problems which help explore that question.

Prometheus
Posts: 28
Joined: Wed Mar 28, 2007 9:58 am UTC
Contact:

Re: "Travelling Salesman Problem" Discussion

Postby Prometheus » Fri Mar 21, 2008 9:49 am UTC

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.
Well I thought it was funny.

MysticTerminator
Posts: 57
Joined: Sat Nov 10, 2007 9:56 am UTC
Contact:

Re: "Travelling Salesman Problem" Discussion

Postby MysticTerminator » Fri Mar 21, 2008 9:56 am UTC

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 real-life XKCD meeting?!

Prometheus
Posts: 28
Joined: Wed Mar 28, 2007 9:58 am UTC
Contact:

Re: "Travelling Salesman Problem" Discussion

Postby Prometheus » Fri Mar 21, 2008 10:00 am UTC

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.
Well I thought it was funny.


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: chridd and 83 guests