Show simple item record

dc.contributor.authorVegh, László A.
dc.descriptionPresented on September 21, 2017 at 1:30 p.m. in the Skiles Building, Room 005, Georgia Tech.en_US
dc.descriptionLászló A. Végh is an Associate Professor at the London School of Economics and Political Science, Department of Mathematics.en_US
dc.descriptionAlgorithms Combinatorics and Optimization (ACO) Colloquium.en_US
dc.descriptionRuntime: 78:56 minutesen_US
dc.description.abstractWe 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 Ola Svensson and Jakub Tarnawski.en_US
dc.format.extent78:56 minutes
dc.publisherGeorgia Institute of Technologyen_US
dc.relation.ispartofseriesSchool of Mathematics Colloquium
dc.relation.ispartofseriesAlgorithms, Combinatorics and Optimization (ACO) Colloquium
dc.subjectApproximation algorithmsen_US
dc.subjectTraveling salesmanen_US
dc.titleA Constant‐Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problemen_US
dc.typeMoving Image
dc.contributor.corporatenameGeorgia Institute of Technology. School of Mathematicsen_US
dc.contributor.corporatenameLondon School of Economics and Political Science. Department of Mathematicsen_US

Files in this item


This item appears in the following Collection(s)

  • ARC Talks and Events [88]
    Distinguished lectures, colloquia, seminars and speakers of interest to the ARC community

Show simple item record