SCS Undergraduate Thesis Topics

In this thesis, we study different variants of the Traveling Salesman Problem under the notion of perturbation resilience or stability as defined by Bilu and Linial. Mihalák et al. defined the notion of stability for Metric Traveling Salesman Problem (where edge weights are symmetric and satisfy the triangle inequality) and provided an algorithm for stable instances. We extend the notion of stable instances to the Asymmetric Traveling Salesman problem and obtain bounds on stability of input instances of asymmetric TSP as well as study the efficacy of Mihalák’s algorithm on asymmetric TSP. We also study the problem of Graphic TSP where the edge weights are given by shortest path metric on an undirected unweighted graph and discuss a possible algorithm for tackling stable instances of Graphic TSP. In this thesis we also provide a summary of the recently published constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem by Svensson, Tarnawski, and Végh.