A (Slightly) Improved Approximation Algorithm for Metric TSP

In the metric traveling salesperson problem (TSP) we are given a list of cities and their pairwise symmetric distances, which form a metric. Our goal is to find the shortest tour that visits every city exactly once. The problem is NP-Hard, and therefore it is unlikely that an efficient algorithm exists which can solve it exactly. However, in 1976 Christofides gave a beautiful 3/2 approximation algorithm for the problem, meaning a polynomial time algorithm which provably returns a tour at most 50% longer than the optimal one. This algorithm is one of the first approximation algorithms ever designed and is routinely used in practice for planning and routing tasks. In this talk I will describe the first approximation algorithm for TSP with approximation ratio below 3/2, representing the first improvement in nearly half a century.