Author: Germano Hüning Neuenfeld Supervisor: prof. Marcel Kenji de Carli Silva
Abstract: The Traveling Salesman Problem (TSP) is central in theoretical computer science and has a myriad of applications. A generalization of the TSP, the Asymmetric Traveling Salesman Problem (ATSP), has a metric version, denoted by mATSP, which admits an approximation algorithm with a polynomial-time computable approximation ratio. This monograph presents a randomized approximation algorithm for the mATSP due to Asadpour, Goemans, Madry, Oveis Gharan, and Saberi, which represented a breakthrough for this problem. Moreover, to understand the Asadpour et al. algorithm, this work presents a collection of tools from areas such as combinatorial optimization, linear programming, and probability theory whose use is standard in the study of approximation algorithms.