Referee’s Comments

• The title should contain the word “approximate” or “heuristic”, or some other indication that the algorithm is not exact.

• Section 1, first para, sentence 3:

“Despite the simplicity of its definition, the ETSP is an NPcomplete problem, that is, the number of possible tours increases exponentially with the number of cities”

I am sure the authors are familiar with the definition of NP-completeness. Implying that it is equivalent to there being an exponential number of tours is quite misleading.

• Section 2, last para: the description of the Extended Parallel Selection Algorithm is inadequate. This algorithm forms an essential part of the following scheme, and the only reference given is to the thesis of one of the authors.

• Same para, sentence 2:

“The extended parallel selection algorithm runs on an EREW PRAM with p processors to find the kth and (k + 1)th smallest elements from a given set S of n elements simultaneously.”

k is a poor choice of variable name here, because k means a different constant throughout the rest of the article.

• Section 3, first para, sentence 2: | S | should be simply S.

• Section 4, first para:

It is claimed that the solution of the recurrence

t(n) = O(1) + O(n^{x}) + 2t(n/k)

satisfies

t(n) = O(n^{x} log(n))

Embarassingly, this appears to be incorrect. Iterating the recurrence gives a geometric series with O(log n) terms. Its sum includes O(n^{x}) terms and O(n^{1/(log_{2} k)}) terms. With the relation between k and x stated in section 2, second para, one has 1/(log_{2} k) = x/(1 − x), and the latter terms dominate. Quick check: Consider k = 4, x = \frac{1}{3} and neglect the O(1) term. Then the recurrence is

t(n) = O(n^{\frac{1}{3}} ) + 2t(n/4)

which is satisfied by t = O(n^{\frac{1}{2}} ).

• Same para, concluding “theorem”: Without a definition of an “approximate Euclidean travelling salesman tour”, this statement is too weak to be designated a theorem, in my opinion.

• Section 5, sentence 8:

“However, as our algorithm is based on Karp’s partitioning algorithm, it should exhibit the same performance as that of Karp’s algorithm […]”

Quite possibly true, but no evidence to this effect is presented. The algorithm described is different to Karp’s in detail.

Recommendations

• The “extended parallel selection algorithm” should be explained.

• The complexity analysis needs to be done more carefully, and the conclusions modified if necessary.

• Some evidence is needed that the algorithm produces acceptably good tours. If theoretical analysis is impossible, empirical results should be be presented. This is not a performance question, and such results can obviously be obtained without coding the algorithm for a parallel computer.

• It would be, however, be nice to see real performance figures for a parallel computer. The EREW model of computation is sufficiently close to existing parallel computers that this should not be impractical.