13 Aug Talk: Arora PTAS for Euclidean TSP
9 views
Skip to first unread message
Vinayak
Aug 10, 2019, 10:31:08 AM8/10/19
to Theory, Évariste Club
Dear all,
I welcome you all for the semester's first Theory Talk to be held next week on Tuesday (13 August 2019). Kindly find the details below:
Speaker: Siddhartha Jain
Title: Arora PTAS for Euclidean TSP
Abstract: The Travelling Salesman Problem (TSP) is one of the most famous problems in Computer Science, but it turns out to be NP-Hard. It's even NP-hard to approximate it to any polynomial factor in the general case! Thankfully we can do a constant (around 1.5) approximation when the distances for which we are solving the problem come from a metric. While exactly what this constant is remains open, we know we cannot have a PTAS in the general case. What's a PTAS? It's a Polynomial Time Approximation Scheme. The idea is that you give me an \epsilon, I will give you a (1+\epsilon) approximation algorithm whose runtime depends on \epsilon but is polynomial in n. So we have runtimes like poly(n) 2^{1/\epsilon} and others.
Sanjeev Arora discovered a PTAS for TSP when the distances come from a Euclidean space a couple of decades ago. This is very good news for Uber and the like, since their distances usually come from the plane! The idea is not hard to understand, and I plan to make the talk accessible to anyone who is comfortable with Dynamic Programming.
Abstract: The Travelling Salesman Problem (TSP) is one of the most famous problems in Computer Science, but it turns out to be NP-Hard. It's even NP-hard to approximate it to any polynomial factor in the general case! Thankfully we can do a constant (around 1.5) approximation when the distances for which we are solving the problem come from a metric. While exactly what this constant is remains open, we know we cannot have a PTAS in the general case. What's a PTAS? It's a Polynomial Time Approximation Scheme. The idea is that you give me an \epsilon, I will give you a (1+\epsilon) approximation algorithm whose runtime depends on \epsilon but is polynomial in n. So we have runtimes like poly(n) 2^{1/\epsilon} and others.
Sanjeev Arora discovered a PTAS for TSP when the distances come from a Euclidean space a couple of decades ago. This is very good news for Uber and the like, since their distances usually come from the plane! The idea is not hard to understand, and I plan to make the talk accessible to anyone who is comfortable with Dynamic Programming.
Venue: TBA
Time: 1:30 - 2:30 pm, 13 August 2019
-- Regards,
Vinayak
Coordinator | Évariste
B.Tech CSE, 3rd Year | IIIT-Delhi
Vinayak
Aug 13, 2019, 3:56:09 AM8/13/19
to Theory, Évariste Club
The venue for the talk is A007.
Reply all
Reply to author
Forward
0 new messages