Mathematical Sciences Department Seminar
Youngho Yoo, Texas A & M
Tuesday, February 4
3:00 - 4:00 pm
Stratton 202
Title: Travelling salesman problem and the Christofides algorithm
Abstract: The travelling salesman problem is one of the most intensively studied problems in computer science and optimization that is of fundamental importance in both theory and practice. It asks, given a list of cities and the distances between pairs of cities, to find the shortest tour visiting every city and returning to the origin city. While finding the optimal tour is an NP-hard problem, in 1976, Nicos Christofides published an elegant algorithm that efficiently computes a tour guaranteed to be within a 3/2 factor of the optimal solution. In this talk I will present this algorithm and prove its approximation guarantee.