Jesper Nederlof

Date: 16:00 – 17:00, Friday, 24.01.2020
Location: Minnaert – 2.02

Title: Finding Cracks in the Wall of NP-completeness: On the Worst-case Complexity of the Traveling Salesman Problem
Abstract: The Traveling Salesman Problem (TSP) is the following notorious computational problem: One is given n cities and distances d(i,j}=d(j,i) between each city i and city j, and one needs to find a round tour with minimum distance visiting all cities.

In this talk we discuss the worst-case complexity of TSP: What is the smallest function T(n) such that any instance of TSP on n cities can be solved with an algorithm that runs in time T(n)? Already in the 1930’s Karl Menger observed T(n) is at most O((n+1)!) since one can try all orderings of the cities, and Menger asked whether this can be significantly improved. In the 1960’s Bellman, Held and Karp showed T(n) is at most  O(n^2 2^n) by employing a (by now) standard technique called `Dynamic Programming’. In the 1970’s NP-completeness theory showed that T(n) is not polynomial unless a major open question in computer science is resolved in an unexpected way.

But this still leaves the following question: Is the algorithm from the 1960’s the best we can do? Or is T(n), say, at most O(1.99^n)? In this talk we discuss why this is an important theoretical question, and outline some recent progress on it for TSP in bipartite graphs.

Afterwards I will discuss how this fits into the picture of my ERC Starting Grant `Finding Cracks in the Wall of NP-completeness’ to be started at February 1 at UU.