[theory students] Theory Students Meeting with Faculty Candidate Nathan Klein -- UPDATED March 20-21 Visit

[Matt Sinclair <sinclair@xxxxxxxxxxx>]

Hi all,

 

Last month I emailed you all asking about a Theory student meeting with our faculty candidate Nathan Klein.  Nathan had to change his visit dates – now Nathan will be coming next week Monday and Tuesday March 20-21.  As part of his interview, Nathan has requested a meeting with the current Theory students (you all!).  Thus, I wanted to reach out and see if a small group of you would be willing to help organize such a meeting?  We have two choices for it:

 

1. A small group of you (~3) could take Nathan to lunch one day during his interview or
2. We could have an hour-long meeting either Monday or Tuesday (not during a meal) where more of you could join.

 

Since Nathan will be here soon, please let me know if this is something you are interested in by Wednesday, 3/15/23.  Likewise, please let me know if you are interested in helping coordinate this meeting with other Theory students.

 

Who: Nathan Klein

 

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.

 

Website: https://homes.cs.washington.edu/~nwklein/

 

Talk Title: A (Slightly) Improved Approximation Algorithm for Metric TSP

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 an approximation algorithm for TSP with approximation ratio below 3/2, representing the first improvement in nearly half a century.

 

Thanks!

Matt