I'm currently doing an internship, in which studying TSP and its algorithms are involved. I'm doing fine with understanding the 2 and 1.5-approximation algorithms for the Metric TSP, but when I come to Arora's PTAS for the Euclidean TSP I get stuck.
I understand what a PTAS is, and I understand the main idea behind Arora's, but when I go deeper into the details, I encounter flaws or simply forgotten specifications (at least from what I understand).
The main article I focus on can be found here : http://algo2.iti.kit.edu/schultes/lebenslauf/publications/euclTSPsummary.pdf
1) When the portals are placed, there's no specification if there are also portals placed on the edges of the bounding box? If not, then how are points that are placed on the edge of the bounding box counted in the algorithm?
2) On page 3 of the article, when computing all valid possibilities of pairings, it is stated :
"Of course, only the possibilities that cover all points inside the square are useful."
So what if a point is placed in a corner of our square (as they always are for the smallest squares)? Is it counted inside the square or not? If yes, then is it also counted inside its neighboring squares sharing the corner? If no, then when and where is the point taken into count for the algorithm?
3) When a point is placed on a portal of one of the smallest squares, and this point is also placed on an edge of a big square, but NOT on a portal of this big square, how can we find a route that passes this edge and simultaneously crosses the point and a portal between the big squares? Can it use the portal of the small square?
If someone can help me with any of my questions, don't hesitate. Thank you for your time.
