According to the abstract, “It is shown that finding a local optimum solution with respect to the Lin-Kernighan heuristic for the traveling salesman problem is PLS-complete, and thus as hard as any local search problem.” This highly technical paper will not have much meaning for the average computer science reader.

The paper states that the Lin-Kernighan (LK) heuristic makes an efficient breadth-first search at level one, and then a depth-first search at the next level. The quality of the local optima for the LK heuristic is impressive.

A question asked in this paper is, How hard is it to produce a local optimum? In a previous paper [1], the author came up with a new complexity class called polymorphic-time local search (PLS). He now sets out to prove that the LK heuristic for the traveling salesperson problem is PLS-complete. Using two lemmas, a proof is given. The explanation is difficult to follow. The author’s definition of “hard” seems incomplete. In several places, he says, “It is easy to see…” when it might be easy to see for the author, but not obvious to the reader. The author should be more complete and more specific in all his explanations. Such statements sound like some bad math textbooks that say, “It is obvious that.…” Professional papers should not make the reader work too hard.

The contributions of this paper are not broad. It deals with a narrow topic in an incomplete way.