Per Austrin: Faster Hamiltonicity
Per Austrin, Theory Group, KTH
Time: Mon 2013-03-25 12.10 - 13.00
Location: Room 4523, Lindstedtsvägen 5, 5th floor, KTH CSC
Lunch is served at 12:00 noon (register at doodle.com/t9hsa8y383qye637 by Thursday Mar 21 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.
Abstract
I will talk about exact algorithms for Hamiltonicity and Travelling Salesperson. The classic Bellman/Held-Karp dynamic programming algorithm for these problems has a running time of O(n^2*2^n). This remained unbeaten for almost half a century until 2010 when Björklund gave an algorithm with running time O(2^{0.73n}) for undirected Hamiltonicity. Since then there has been a flurry of generalizations and simplifications, but many open questions remain.
My aim for the first part is to describe the state of the art and some general techniques that are used, and for the second part to go over one or two algorithms in detail.
The talk should be accessible without any specific background knowledge and in particular you don't need to know what the Hamiltonicity and Travelling Salesperson problems are beforehand.