University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

## A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman ProblemAdd to your list(s) Download to your calendar using vCal - Lazlo Vegh (LSE)
- Tuesday 23 January 2018, 15:00-16:00
- Physics West 106.
If you have a question about this talk, please contact Allan Lo. 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 Ola Svensson and Jakub Tarnawski. This talk is part of the Combinatorics and Probability Seminar series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsFilling in the blank – I will be ….... in 2050’ IMA West Midlands Branch Type the title of a new list here## Other talksThe Suzuki Chain Post-mortem privacy – theory, law and technology An attack on ECDSA using lattice techniques Physics at van der Waals interfaces: Twists, incommensurability and emergent phenomena Combining Organic Synthesis, Isotopes and Synthetic Biology in Natural Products Research School Seminar |