*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Breakthroughs in Approximation Algorithms for
Traveling Salesman Problems (TSP)
Lecture series by Ola Svensson (EPFL)
Tuesday, April 23 - Thursday, April 25, 2019
10am - noon daily in Groseclose 402
Schedule:
Tuesday, April 23, 2019
10:00am - 12:00pm Lecture 1: The symmetric TSP (Groseclose 402)
12:00pm - 1:00pm Lunch
3:30pm - 4:00pm Problem Solving Session (Klaus 2222)
Wednesday, April 24, 2019
10:00am - 12:00pm Lecture 2: Different approaches for asymmetric TSP (Groseclose 402)
12:00pm - 1:00pm Lunch & Poster Session
3:30pm - 4:00pm Problem Solving Session (Klaus 2222)
Thursday, April 25, 2019
10:00am - 12:00pm Lecture 3: A constant-factor approximation algorithm for asymmetric TSP (Groseclose 402)
12:00pm - 1:00pm Lunch
3:30pm - 4:00pm Problem Solving Session (Klaus 2222)
Abstract: The traveling salesman problem is one of the most fundamental optimization problems. Given n cities and pairwise distances, it is the problem of finding a tour of minimum distance that visits each city once. In spite of significant research efforts, current techniques seem insufficient for settling the approximability of the traveling salesman problem. This status is particularly intriguing as a natural and several-decade-old linear programming relaxation is believed to give better guarantees than we are currently able to prove!
In this mini-course, we will overview of old and new approaches for settling this question. We shall, in particular, talk about recent developments for the asymmetric traveling salesman problem.
Bio: Ola Svensson is an Associate Professor at the School of Computer and Communication Sciences at EPFL, Switzerland. He is interested in theoretical aspects of computer science with an emphasis on the approximability of NP-hard optimization problems. His work has received several recognitions including the 2019 Michael and Sheila Held Prize by the National Academy of Sciences and best paper awards at FOCS and STOC.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
