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.

  • $\begingroup$ For questions 1 and 2 couldn't you just come up with some arbitrary tie-breaking rule? Like each square contains its north and east edges but not its south and west edges? $\endgroup$ Feb 28, 2017 at 12:44
  • $\begingroup$ @SashoNikolov, this can solve question 2 yes, although I don't see how it would help in question 1 $\endgroup$
    – J. Schmidt
    Feb 28, 2017 at 14:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.