log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
A (Slightly) Improved Approximation Algorithm for Metric TSP
Nathan Klein
IRB 4105, Zoom link-https://umd.zoom.us/j/92977540316?pwd=NVF2WTc5SS9RSjFDOGlzcENKZnNxQT09
Thursday, March 16, 2023, 11:00 am-12:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract

In the metric traveling salesperson problem (TSP) we are given a list of cities and their pairwise symmetric distances, which form a metric. Our goal is to find the shortest tour that visits every city exactly once. The problem is NP-Hard, and therefore it is unlikely that an efficient algorithm exists which can solve it exactly. However, in 1976 Christofides gave a beautiful 3/2 approximation algorithm for the problem, meaning a polynomial time algorithm which provably returns a tour at most 50% longer than the optimal one. This algorithm is one of the first approximation algorithms ever designed and is routinely used in practice for planning and routing tasks. In this talk I will describe the first approximation algorithm for TSP with approximation ratio below 3/2, representing the first improvement in nearly half a century. 

 

 

Bio

Nathan Klein is a final year Ph.D. student at the University of Washington where he is advised by Anna Karlin and Shayan Oveis Gharan. His primary research interest is studying approximation algorithms for classical optimization problems. He has received a best paper award at STOC 2021 and an NSF GRFP fellowship for his work on the traveling salesperson problem.

This talk is organized by Richa Mathur