BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Combinatorics and Probability Seminar
SUMMARY:A Constant-Factor Approximation Algorithm for the
Asymmetric Traveling Salesman Problem - Lazlo Vegh
(LSE)
DTSTART:20180123T150000Z
DTEND:20180123T160000Z
UID:TALK3040AT
URL:/talk/index/3040
DESCRIPTION: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 resul
t confirms the conjectured constant integrality ga
p of that relaxation. Our techniques build upon th
e constant-factor approximation algorithm for the
special case of node-weighted metrics. Specificall
y\, we give a generic reduction to structured inst
ances that resemble but are more general than thos
e arising from node-weighted metrics. For those in
stances\, we then solve Local-Connectivity ATSP\,
a problem known to be equivalent (in terms of cons
tant-factor approximation) to the asymmetric trave
ling salesman problem. This is joint work with Ola
Svensson and Jakub Tarnawski.
LOCATION:Physics West 106
CONTACT:Allan Lo
END:VEVENT
END:VCALENDAR