In 1996 Sanjeev Arora published a polynomial time approximation scheme for the Euclidean Travelling Salesman Problem. I'd like to know whether anyone is aware of empirical results arising from an actual implementation of his algorithm.
Sahil Mahajan
I tried to implement Sanjeev Arora's improved PTAS which he published in 1998. It's running time is better than 1996 version. I found out that it can't be implement exactly. Memory requirement for storing dynamic programming solution reaches about 2^130 for very trivial cases. So to implement it, one would also have to approximate dynamic programming solution but doing so would make algorithms loose its theoretical guarantees. I also read 1996 paper and doubt if that could be implemented.
0 votes
0 thanks
- Badges
- Science topic
- Similar topics
- Mathematics
More Benjamin Garrett's questions See All
Similar questions and discussions