Welcome to Quantum Magazine's podcast.

Each episode, we bring you stories about developments in science and mathematics.

I'm Susan Vallett.

When Nathan Klein started graduate school two years ago, his advisors proposed a modest plan

to work together on one of the most famous long-standing

problems in theoretical computer science, the traveling salesperson problem.

Even if they didn't manage to solve the traveling salesperson problem, they figured Klein

would learn a lot in the process.

He went along with the idea. I think probably I didn't know to be intimidated as much. You know, just like a first year

guy who I don't know what's going on. So they're like, okay, here's this problem. I'm like,

okay, I'll think about it. Now, in a paper posted online in July, Klein and his advisors at the

University of Washington, Anna Carlin,

and Cheyenne Ovese Baran, have finally achieved a goal computer scientists have pursued for nearly

half a century. They found a better way to find approximate solutions to the traveling

salesperson problem. This optimization problem seeks the shortest or least expensive round trip through a collection of cities.

It has applications ranging from DNA sequencing to ride-sharing logistics.

Over the decades, it's inspired many of the most fundamental advances in computer science,

helping to illuminate the power of techniques, such as linear programming.

But researchers have yet to fully explore its possibilities, and not because they didn't try.

The traveling salesperson problem isn't a problem.

It's an addiction, as Christos Papadimitro,

a leading expert in computational complexity is fond of saying. Most computer scientists believe that

...