Re: [theory students] Theory Lunch TODAY: TCS+ talk by Ola Svensson

[Benjamin Miller <bmiller@xxxxxxxxxxx>]

Hi all,

Just a reminder that theory lunch and the TCS+ talk are happening in about an hour. See you there!

Benjamin

On Mon, Nov 6, 2017 at 6:15 PM, Benjamin Miller <bmiller@xxxxxxxxxxx> wrote:

Hi all,

We'll have theory lunch on Wednesday in CS 3310, starting at noon so that we can catch the TCS+ talk. Ola Svensson will be presenting a recent breakthrough on ATSP (see below). It should be a good talk! As usual, bring your own lunch. See you there.

Benjamin

Title: A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem Abstract: We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem. This is joint work with Jakub Tarnawski and LÃszlà VÃgh.