| 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: 7⁄5-approximation for graphic TSP, 3⁄2 for the path version, and 4⁄3 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 3⁄2+1⁄34 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. |