
\documentstyle{article}

\begin{document}

\section*{Referee's Comments}

\begin{itemize}
\item
The title should contain the word ``approximate'' or ``heuristic'', or
some other indication that the algorithm is not exact.
\item
Section 1, first para, sentence 3:
\begin{quote}
``Despite the simplicity of its definition, the ETSP is an NP-complete
problem, that is, the number of possible tours increases exponentially
with the number of cities''
\end{quote}
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.
\item
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.

\item
Same para, sentence 2:
\begin{quote}
``The extended parallel selection algorithm runs on an EREW PRAM
with $p$ processors to find the $k$th and $(k+1)$th smallest elements
from a given set $S$ of $n$ elements simultaneously.''
\end{quote}
$k$ is a poor choice of variable name here, because $k$ means a
different constant throughout the rest of the article.

\item
Section 3, first para, sentence 2:  $\mid S \mid$ should be simply $S$.

\item
Section 4, first para:  

It is claimed that the solution of the recurrence
\begin{displaymath}
t(n) = O(1) + O (n^x) + 2 t(n/k)
\end{displaymath}
satisfies
\begin{displaymath}
t(n) = O(n^x \log (n))
\end{displaymath}
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
\begin{displaymath}
t(n) = O (n^\frac{1}{3}) + 2 t(n/4)
\end{displaymath}
which is satisfied by $t = O(n^\frac{1}{2})$.

\item
Same para, concluding ``theorem'':  Without a definition of an ``{\em
approximate} Euclidean travelling salesman tour'', this statement is
too weak to be designated a theorem, in my opinion.

\item
Section 5, sentence 8:
\begin{quote}
``However, as our algorithm is based on Karp's partitioning algorithm,
it should exhibit the same performance as that of Karp's algorithm
[\ldots]''
\end{quote}
Quite possibly true, but no evidence to this effect is presented.  The
algorithm described is different to Karp's in detail.
\end{itemize}

\section*{Recommendations}

\begin{itemize}
\item
The ``extended parallel selection algorithm'' should be explained.

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

\item
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 {\em performance}
question, and such results can obviously be obtained without
coding the algorithm for a parallel computer.

\item
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.
\end{itemize}

\end{document}

