Travelling Salesman

Date Topic Presenter Info
May 5, 2017 Classic results and overview of the results from the chosen papers Laura Sanita
May 15, 2017 “Approximating Graphic TSP by Matchings” (2011) by Tobias Momke, and Ola Svensson Matthew Buckley Here is a talk by Naveen Garg Approximating Graphic TSP by Matchings
May 19, 2017 “Shorter Tours by Nicer Ears: 75-approximation for graphic TSP, 32 for the path version, and 43 for two-edge-connected subgraphs” (2012) by Andras Sebo, and Jens Vygen Justin Toth
May 26, 2017 “On the metric s-t path Travelling Salesman Problem” (2014) by Zhihan Gao Andre Linhares
June 2, 2017 “Better s-t-Tours by Gao Trees” (2015) by Corinna Gottschalk, and Jens Vygen Martin Gross A talk by Jens Vygen, Reassembling trees for the travelling salesman leads up to the result of Corinna Gottschalk and Jens Vygen. Please note that recently Frans Schalekamp Andras Sebo, Vera Traub, and Anke van Zuylen provided a short proof of the key structural result of Corinna Gottschalk and Jens Vygen.
June 9, 2017 “The Salesman’s Improved Paths: A 32+134 Approximation” (2016) by Andras Sebo, and Anke van Zuylen Andras Sebo The algorithm, the main proof of the analysis and the intuition behind its ingredients will be explained, including the gain of using Gottschalk and Vygen’s particular convex combination of spanning trees, and how Schalekamp, Sebo, Traub, and van Zuylen finally managed to use matroid union in “Layers and matroids for the travelling salesman’s paths (2017) for a simple algorithmic proof of this particular convex combination.
June 16, 2017 “Polynomial-Time Separation of a Superclass of Simple Comb Inequalities” (2006) by Lisa Fleischer, Adam Letchford, and Andrea Lodi Quincy Lap-Kwan Lam
June 23, 2017 Questions and Discussion Session with Sylvia Boyd and Andras Sebo
June 30, 2017 IPCO Break. This Friday we have no talks
July 7, 2017 “An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem” (2010) by Arash Asadpour, Michel Goemans, Aleksander Madry, Shayan Oveis Gharan, and Amin Saberi Akshay Ramachadran Here is a talk by Shayan Oveis The Asymmetric Traveling Salesman Problem
July 14, 2017 “Approximating ATSP by Relaxing Connectivity” (2015) by Ola Svensson Zhuan Khye Koh Here is a talk by Ola Svensson Approximating ATSP by Relaxing Connectivity
July 21, 2017 SiGMa break. This Friday we have no talks.
July 28, 2017 “Constant Factor Approximation for ATSP with Two Edge Weights” (2015) by Ola Svensson, Jakub Tarnawski, and Laszlo Vegh Sharat Ibrahimpur
Aug 4, 2017 “Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP” (2014) by Nima Anari, and Shayan Oveis Gharan Akshay Ramachadran and Julian Romero This talk does not assume any previous reading. Further reading: Nikhil Srivastava’s blog post Discrepancy, Graphs, and the Kadison-Singer Problem. Please also take a look at the course Recent Developments in Approximation Algorithms by Shayan Oveis Gharan. In Lecture 18 and 19 of this course, the results from the above paper were presented.