4

I'm willing to implement an algorithm to solve the 2-dimensional Euclidian version of the Traveling Salesman Problem in the most efficient way (i.e. most accurate result + least time). While doing my research I found plenty of algorithms but Arora's 1998 paper and its presentation struck me as maybe the best ones for that purpose. There are other versions of the solution using the same idea such as the one by Schultes in 2004. The problem is that it seems incredibly hard (if not impossible) to implement it and I found no records of anyone ever doing so in an accessible way even though it's been almost 20 years since the paper was first published.

Is there any existing implementation or at least a guideline for that matter? If not, what would be an existing and implementable algorithm to substitute it as best as possible?

Gabriel Rebello
  • 1,077
  • 1
  • 11
  • 17

2 Answers2

6

I will take you at your word when you say you are "ready" to implement this, but there are good reasons you aren't finding source code lying around.

Aside from the complexity, a "practical problem with PTAS is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is O(n(1/ε)!)." This leads to even more rigid requirements like EPTAS and FPTAS, although I don't believe TSP currently has solutions at these stricter requirements. So bear in mind that a PTAS solution doesn't necessarily eliminate wide variability as you vary the approximation parameter.

The most applicable paper I've found to your post is An Empirical Analysis of Approximation Algorithms for Euclidean TSP .

An innovative Polynomial-Time Approximation Scheme (PTAS) for the Euclidean TSP was given by Sanjeev Arora. To date, there is no evidence that it can be implemented to be practically useful. In light of this, we propose an implementation of the Euclidean TSP that is based on the essential steps of the Arora’s PTAS and adds some heuristics to improve the running time.

The authors do not provide a link to their C++ implementation but you could try emailing them. The more important aspect of their paper is the quantitative comparisons they made of their Arora-based approach vs. 4 other competitive algorithms provided in the Concorde solver. Their paper concludes:

Experimental results show that Arora´s PTAS is practically feasible. Table I and Table II show that in spite of its good performance, it seems that our approach must be improved to generate more approximate solutions. In most cases the significant theoretical results are lost due to implementation decisions. We think the quality of the solutions had to do with implementation aspects linked to data structures and the need to give more hints about which portals must be used by the tour.

If you read their paper in detail, you will see they made various implementation decisions and optimizations, many of which are likely sub-optimal and/or not rigorously justified. Read the results for yourself, but it seems to me that their PTAS algorithm completed in 0.25x to 1.0x the time of the other algorithms on average, but the results were sometimes substantially worse. It seems to me the biggest risk here is the "implementation decisions" and heuristics you may need to trial-and-error in hopes of actually realizing those elusive performance benefits.

Special Sauce
  • 5,338
  • 2
  • 27
  • 31
  • 2
    The way I see it, they didn't implement the PTAS version. From section 2.2 of the paper: "Because of this practical reason we decided to place the portals in such a way that there is at most one portal communicating neighbors` squares." – Felix S Mar 31 '17 at 13:33
0

I guess it's no longer relevant, but the authors of the paper Special Sauce mentioned in fact published their code on GitHub: https://github.com/barbaramartina/C---TSP-Arora-Implementation/tree/master/TSP_Implementation

However, I'm also looking for an exact implementation, so if you implemented something I'd be very grateful if you could post a link to your implementation here :)

Layla
  • 125
  • 10
  • Welcome to Stack Overflow! While links are great way of sharing knowledge, they won't really answer the question if they get broken in the future. Add to your answer the essential content of the link which answers the question. In case the content is too complex or too big to fit here, describe the general idea of the proposed solution. Remember to always keep a link reference to the original solution's website. See: [How do I write a good answer?](https://stackoverflow.com/help/how-to-answer) – sɐunıɔןɐqɐp Jul 27 '18 at 07:29