Though awarded the IMU Abacus Medal 2026 for a wide range of achievements that bring seemingly disparate mathematical ideas together to solve problems at the forefront of theoretical computer science, Iranian computer scientist Shayan Oveis Gharan is perhaps best known for his work on the travelling salesperson problem (TSP).

In his Laureate Lecture at the 13th Heidelberg Laureate Forum, Oveis Gharan described the tools he developed, and subsequently applied to several open problems – most notably in making a major theoretical breakthrough in the TSP after over four decades of stagnation.

The Trials of a Travelling Salesperson

First mathematically formulated in 1930, the TSP simply asks: If a travelling salesperson needs to visit several cities and knows the distances between each pair of cities, what is the shortest possible route they can take so that they visit each city exactly once before returning home? A classic optimisation conundrum, TSP may appear simple but becomes increasingly challenging the more cities the hard-working salesperson has to visit.

Using brute force methods (checking every route and selecting the shortest), it can be solved exactly if the salesperson only needs to visit a handful of cities. But even if they visit just 12 cities (including their home city), almost 20 million routes must be evaluated (\((12 – 1)! / 2 = 11! / 2 = 19,958,400\) unique closed routes for symmetric TSP, i.e. assuming the distance between any two cities is the same in both directions).

Though this would hardly challenge a modern computer, adding just eight more cities pushes the number of routes to around \(6 \times 10^{16}\). An NP-hard problem, using simple brute force sees the worst-case runtime grow exponentially with the number of cities.

Better methods were first developed in the 1950s. A seminal paper by George Dantzig, Ray Fulkerson and Selmer Johnson of the RAND research organisation introduced the cutting-plane method. In rough terms, this approach drops the requirement that each route between cities must be realistic, transforming the problem into an easily solved ‘relaxed’ linear programming puzzle. Quickly solved, unrealistic portions of the solution are easy to identify, and then exclude (or ‘cut’), creating a modified linear program that can then be solved. When the researchers iteratively applied this method to a TSP of 49 US cities, instead of millions of steps, they needed just 26 cuts to reach the optimal 12,345-mile solution.

Getting as Close to a Solution as Possible

Of course, as the number of cities grows, at some point even this method becomes computationally unrealistic, as Oveis Gharan summarised in his lecture: “If the number of cities grows a lot, like hundreds or thousands of cities, with \(n!\) possibilities, then we cannot compute it,” he said. “So what do we do instead? Instead, in theory, we look for so-called approximation algorithms.”

It was not until 1976 that a useful approximation algorithm was devised. Nicos Christofides managed to find a way of approximating solutions for a flavour of the TSP known as the metric TSP; where the distances between cities must obey the triangle inequality (and be non-negative and symmetric).

Instead of solving the metric TSP directly, his algorithm finds the minimum spanning tree (MST), i.e. the most efficient possible way to connect nodes (cities) together so that every point is reachable without creating any closed loops or cycles. It then finds a minimum-weight perfect matching on the set of odd-degree vertices to make the graph Eulerian (i.e. where a single continuous trail can visit every edge exactly once, requiring every vertex to have an even degree) so that an Eulerian circuit can be formed. In fact, taking this approach guarantees a polynomial-time route at most 50 percent longer than (or 1.5x the length of) the absolute shortest possible route for any instance of the metric TSP.

A Slight Improvement Makes a Big Difference

For decades, this stood as the closest anyone could come to an exact solution. But during his PhD in the early 2010s, Oveis Gharan started interrogating Christofides’ algorithm. He saw that the key bottleneck was the first step in the algorithm, because it selects edges deterministically, which can create localised pockets of odd-degree vertices that are very expensive to match.

Focusing on this weakness, he started to explore alternative angles to attack. Specifically, he took advantage of the polynomial paradigm, which he explained in his lecture as follows: “Let’s say you have an algorithm that you’re trying to analyse; maybe there’s a probability distribution over a large chunk of objects that you cannot even write down in your computer,” he said. “You can start by writing a polynomial of these objects, and then … study its properties – roughly speaking, you understand global properties of your probability distributions using polynomials.”

With this approach, he managed to make a slight improvement on Christofides’ work for a special case in 2011. By 2020, he had developed this technique significantly. Instead of taking the absolute cheapest spanning tree as Christofides’ algorithm did, Oveis Gharan alongside Anna Karlin and Nathan Klein, had an algorithm that picked a randomised tree sampled from a maximum entropy distribution (a probability distribution designed to be as unbiased and maximally random as possible while respecting specific constraints), guided by the relaxed linear programming introduced by Dantzig and colleagues in the 1950s. With this, the researchers managed to ever so slightly improve on Christofides’ work – shrinking the 1.5x figure by \(10^{-36}\).

Though infinitesimally small by some standards, for those that have obsessed over the TSP for most of their careers this result was truly ground-breaking. “We managed to do a little bit better,” said Oveis Gharan. “But the point of this is that [Christofides’ algorithm] is not the limit of efficient algorithms.” It is hoped that Oveis Gharan’s new way of approaching the problem and the tools he and his colleagues have developed will lead to further improvements, perhaps eventually even the absolute limit of approximation. “Many people are trying to improve this algorithm – I expect [the limit] to be something like 1.4x,” Oveis Gharan explained. “I don’t know how to do it, but that’s something interesting to explore.”