Date: | Mon, 06 Nov 2017 18:15:30 -0600 |
---|---|
From: | Benjamin Miller <bmiller@xxxxxxxxxxx> |
Subject: | [theory students] Theory Lunch Wednesday: TCS+ talk by Ola Svensson |
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-Connectiv |
[← Prev in Thread] | Current Thread | [Next in Thread→] |
---|---|---|
|
Previous by Date: | [theory students] Theory Lunch today at 12:30 in 3310, Benjamin Miller |
---|---|
Next by Date: | Re: [theory students] Theory Lunch TODAY: TCS+ talk by Ola Svensson, Benjamin Miller |
Previous by Thread: | Re: [theory students] Theory Lunch TODAY: TCS+ talk by Ola Svensson, Benjamin Miller |
Next by Thread: | [theory students] Theory seminar: action needed, Shuchi Chawla |
Indexes: | [Date] [Thread] |