traveling salesperson problem – Quanta Magazine

Researchers Approach New Speed Limit for Seminal Problem

Lakshmi Chandrasekaran — Mon, 29 Jan 2024 15:11:07 +0000

The traveling salesperson problem is one of the oldest known computational questions. It asks for the ideal route through a certain list of cities, minimizing mileage. Despite seeming simple, the problem is notoriously difficult. While you can use brute force to check all the possible routes until you find the shortest path, such a strategy becomes untenable after just a handful of cities. Instead...

Source

What Makes Quantum Computing So Hard to Explain?

Scott Aaronson — Tue, 08 Jun 2021 15:10:05 +0000

Quantum computers, you might have heard, are magical uber-machines that will soon cure cancer and global warming by trying all possible answers in different parallel universes. For 15 years, on my blog and elsewhere, I’ve railed against this cartoonish vision, trying to explain what I see as the subtler but ironically even more fascinating truth. I approach this as a public service and almost my...

Source

Computer Scientists Break Traveling Salesperson Record

Erica Klarreich — Thu, 08 Oct 2020 16:15:46 +0000

When Nathan Klein started graduate school two years ago, his advisers proposed a modest plan: to work together on one of the most famous, long-standing problems in theoretical computer science. Even if they didn’t manage to solve it, they figured, Klein would learn a lot in the process. He went along with the idea. “I didn’t know to be intimidated,” he said. “I was just a first-year grad student...

Source

Mystery Math Whiz and Novelist Advance Permutation Problem

Erica Klarreich — Mon, 05 Nov 2018 14:50:07 +0000

On September 16, 2011, an anime fan posted a math question to the online bulletin board 4chan about the cult classic television series The Melancholy of Haruhi Suzumiya. Season one of the show, which involves time travel, had originally aired in nonchronological order, and a re-broadcast and a DVD version had each further rearranged the episodes. Fans were arguing online about the best order to...

Source

One-Way Salesman Finds Fast Path Home

Mark Kim-Mulgrew — Thu, 05 Oct 2017 13:00:37 +0000

A salesman has to visit every major city in the U.S. What is the cheapest way to hit them all exactly once and then return to the headquarters? The computation of the single best answer for what is known as the traveling salesman problem is famously infeasible. Nevertheless, computer scientists have long known how to find a pretty good route — one that incurs no more than 1.5...

Source