CLOSE

# Solving the Traveling Salesman Problem

The Traveling Salesman Problem (TSP for short) is a classic problem in computer science. Wikipedia succinctly states the problem like so:

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

First formalized in 1930, the TSP has been studied and fiddled with ever since. There are lots of ways to try solving the problem, but the devil is in the details. Most of us start with a simple assumption: Let's pick a starting city, then just start walking around the map, choosing the nearest city every time. Rinse, repeat. This algorithm is called "Greedy," and while it does a reasonable job for very short routes, it often fails to make the overall route the shortest, because it doesn't consider the entire route. (It "greedily" chooses the optimal choice in each leg of the route, at the possible expense of the larger route.)

Take a look at this video, illustrating several algorithms for solving the TSP, and compare the complexity of the solutions. Computers are rad.

Read more about this video from its creator, James "poprhythm" Kolpack. For a lot more on this problem and why it matters, check out this lecture.

[h/t: Kottke.]

iStock
arrow
language
As Big as a What? How Literary Size Comparisons Change Over Time
iStock

Many humans are bad at visualizing what measurements really mean unless you give them a comparison. Tell someone a space is 360 feet long and they'll probably just blink; say it's the length of a football field and you might get a nod of comprehension. That's why many writers use size comparisons rather than precise measurements in non-technical works. (It also helps convince people your work wasn't written by a robot.) But the comparisons that writers use reflect the culture and time period they're in—tell an ancient Roman something is the size of a credit card or a car, and you're not going to get very far.

As spotted by Digg, programmer and data visualization whiz Colin Morris recently performed an experiment that demonstrates how these kinds of object comparisons change over time. Morris mined the vast Ngram dataset of English-language Google Books for occurrences of the phrase "the size of ___" between 1800 and 2008, then ranked the top results by popularity overall and in specific centuries. Some of the results made perfect sense (England has phased out the shilling; basketball didn't exist for most of the 1800s), while others were more surprising (why did we stop referring to cats as a popular size comparison in the 21st century?).

Overall, Morris found that items from the natural world have fallen into decline as reference points, while sports analogies have exploded onto the scene. (Morris wonders whether this has to do with the rise of leisure time, and/or the mass media that exposes far more spectators to sports than ever before.) Some of the specific results also have intriguing stories to tell: We no longer talk about the size of pigeon's eggs largely thanks to the extinction of the passenger pigeon, which was once the most numerous bird in the United States. The numbers of city pigeons just don't compare—when was the last time you saw one of their eggs?

There is one clear winner across the centuries, however: peas. These tiny legumes were the most popular reference point in the 1800s and they remain so today. The same is true of runner-up the walnut. Let it not be said we have nothing in common with our ancestors.

Here are the top five items in each century that Morris investigated:

1800s

1. pea
2. walnut
4. egg
5. hen's egg

1900s

1. pea
2. walnut
4. egg
5. orange

2000-2008

1. pea
2. walnut
3. quarter
4. football field
5. egg

For the full list, head over to Colin Morris's site.

[h/t Digg]

John Lamparski/Getty Images for Hulu
arrow
#TBT
The Highs and Lows of the Dell Dude
John Lamparski/Getty Images for Hulu

Benjamin Curtis was just 19 years old when he went to the open audition that would change his life, but he still felt like a senior citizen. He was surrounded by child actors from the ages of 12 to 17, most of them accompanied by their mothers. The group was part of a casting call for Dell, the personal computing company well-known to business and educational customers but an unproven commodity for the home market.

Dell’s ad agency, Lowe Worldwide, hoped to change that reputation by introducing the character of Steven, a sharp, tech-savvy teen who would extol the virtues of Dell’s desktop and laptop offerings in a charmingly goofy manner. Even though he was two years outside the age range, Curtis’s agent believed he had a shot.

He read. And read again. And then read a third time. By December 2000, Curtis had gotten the part and was quickly becoming known as the “Dell Dude,” a pitchman who rivaled the Maytag Man in terms of commercial popularity. But by 2003, the character would disappear, victimized by a peculiar kind of corporate hypocrisy. While the Dell Dude’s stoner wisdom was good for laughs and increased sales, Curtis being arrested for actual marijuana possession was not.

In 1984, Michael Dell was a pre-med student at the University of Texas when he began tinkering with home computing hardware. A serial entrepreneur—he once made \$18,000 as a teenager collecting data to find new subscribers for the Houston Post—Dell figured that custom machines and aggressive customer support would help fill a niche in the growing PC market.

He was right. Dell racked up \$1 million in sales that year and spent the next decade and a half expanding into a billion-dollar enterprise. But a lot of Dell’s business consisted of commercial accounts like schools and government offices, leaving direct-to-consumer sales largely untapped. To help introduce Dell to those users, the company hired Lowe Worldwide to create a campaign that would appeal to people who felt intimidated by the personal computing phenomenon.

Lowe conceived of a precocious kid who could rattle off Dell’s specs and lend a human face to their line of hardware. But the “Dell Dude” wasn’t fully realized until Curtis walked in the door.

Originally from Chattanooga, Tennessee, Curtis grew up interested in performing magic and drifted toward theater in an attempt to strengthen his stage presence. He went on to earn an acting scholarship to New York University and had a roommate who knew a commercial talent agent. Having been introduced to her, he began going out on casting calls. One of them was for Dell.

Embodied by Curtis, the Steven character morphed into a Jeff Spicoli-esque surfer archetype, fast-talking and charming. In his first appearance, Steven makes a videotaped appeal to his father for an \$849 Dell desktop “with a free DVD upgrade” because he knows his dad “likes free stuff.” In another, he encourages a friend’s family to gift his buddy with a Dell for \$799, complete with an Intel Pentium III processor.

The commercials debuted in 2000, but it wasn’t until DDB, the Chicago ad agency that took over Dell’s account, introduced a catchphrase that Steven acquired his nickname. In his fourth commercial, he announced to his friend, “Dude you’re getting a Dell!”

From that point on, Dell’s splash into residential home computing was guaranteed. Sales rose 100 percent, with Dell’s market share growing by 16.5 percent. The awareness was almost exclusively the result of Curtis’s popularity, which grew to include numerous online fan pages and calls for personal appearances. Younger viewers wrote in and wondered if he was available for dates; older viewers considered him a non-threatening presence.

By 2002, Steven had starred in more than two dozen Dell spots. In some of the later ads, he took a back seat, appearing toward the end of the ads. The cameos prompted some concern among fans that Dell would be sidelining Curtis, but company representatives denied it. In early 2003, however, the Dell Dude found himself out of a job.

“Dude, you’re getting a cell” was the headline in media accounts of Curtis’s arrest in February 2003 on suspicion of attempting to purchase marijuana. Curtis was on Manhattan’s Lower East Side and sporting a kilt he recently acquired in Scotland when an undercover officer spotted him purchasing the drug from a dealer. After being held in custody overnight, Curtis was released and the case was adjourned. If he stayed out of trouble for a year, his record would be expunged.

The New York Times compared the relative innocuousness of his arrest to that of actor Robert Mitchum, who was arrested on a marijuana-related charge in 1948. Despite living in a more conservative era, Mitchum’s career was largely unaffected. The same didn’t hold true for Curtis, however; he was promptly dropped by Dell as their spokesperson. According to Curtis, the company had a strict no-drugs policy for employees, and one strike was all it took to force his dismissal.

Feeling ostracized from commercial work and typecast by the role, Curtis juggled gigs while working at a Mexican restaurant in New York and enduring daily recognition from customers. “They’ll get really drunk, and they’ll start yelling things at me,” he told Grub Street in 2007. “I either ignore them, or if it’s way out of hand, I go up and say, ‘I appreciate your support, but my name is Ben.’ That usually doesn’t work so I smile and ignore them.”

Dell never found a mascot as well-liked as Curtis. They hired singer Sheryl Crow to appear in spots beginning in 2005, but she didn't sway consumers as much as Steven had. In 2010, the company attempted to battle back from negative press over selling defective computers to customers between 2003 and 2005. Today, they typically occupy a list of the top three PC companies, trailing Lenovo and HP.

Curtis, meanwhile, made a segue into off-Broadway performing and now operates Soul Fit NYC, a holistic wellness center in New York that offers yoga, massage, personal training, and life coaching services. Although he’s expressed interest in coming back to Dell as a spokesperson, the company may not appreciate his latest indiscretion: In 2013, he admitted to owning a MacBook.

### SECTIONS

arrow
LIVE SMARTER
arrow
LIVE SMARTER
More from mental floss studios