This meeting is in preparation for the TSP lecture series ARC will be holding from April 23rd to April 25th.

Here are some recommended topics and papers to cover:

  1. Symmetric TSP: The 3/2 Approximation by Christofides. https://en.wikipedia.org/wiki/Christofides_algorithm
  2. Asymmetric TSP: The log n Approximation by by Frieze Gabliati and Maffioli.
  3. Symmetric and Asymmetric TSP: Held-Karp LP relaxation.
  4. (Advanced): Uncrossing and laminarity for LPs. https://www.cc.gatech.edu/~vempala/papers/tsp.ps

The following paper https://arxiv.org/pdf/1104.3090.pdf was written by the ARC speaker (Ola Svensson) and Tobias Momke has some good overview of previous results as well as some new interesting techniques. These resources should help you utilize the ARC Colloq mini course to the fullest!

Previous: Elections

We’ll be electing new officers and talking about future

continue reading ❯