-1
$\begingroup$

In his 2009 paper General k-opt submoves for the Lin–Kernighan TSP heuristic, Helsgaun defines the local tour improvements on which the LKH heuristics are based as:

Excerpt from Helsgaun's paper

with a cycle defined here: Helsgaun's definition of cycles in symmetric graphs

which clearly rules out multiple occurences of vertices in cycles, disproving user197309's claim that uniqueness of vertices can't be concluded from the definition of cycles.
Uniqueness of vertices in cycles also reflects common understanding in the sense of what definitions in publictions amount to.

several questions arise from that definition of admissible $k$-Opt moves:

  • Where is the proof that the set of exchanged edges must form a cycle?
  • Why aren't adjacent tour edges considered as exchange candidates?

Here is a simple counter example to the neessity of the single-cycle conjecture and to the non-adjacent tour edges assumption plus is it a cheaper $3$-Opt move than the ones requiring non-adjacent tour edges:

Counter example to Helsgaun's k-Opt moves conjecture

  • One pair of the red tour edges that are exchanged with the solid black edges is adjacent.
  • The union of exchanged tour-edges with the replacement edges consists of two vertex-disjoint cycles depicted by the thin ellipses.
  • The exchange of the edges resembles a transition between tours.
Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I’m voting to close this question because, of your 5 questions, only 2 are mathematical. The others might belong on AcademiaSE. $\endgroup$
    – LSpice
    Apr 26, 2021 at 15:16

1 Answer 1

Reset to default
5
$\begingroup$

The criticism of the paper is wrong. The reader has erroneously assumed that the t's for a move must be different.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I tend to agree (with the criticism of the question). Also, Springer is a publisher and those are not in charge of peer review. $\endgroup$
    – Sam Sanders
    Apr 26, 2021 at 17:27
  • $\begingroup$ The paper states that sequence of edges forms a cycle, which is [ is a subset of the edge set of G that forms a path such that the first node of the path corresponds to the last](mathworld.wolfram.com/GraphCycle.html); [a sequence {x_1,x_2,...,x_n} such that (x_1,x_2), (x_2,x_3), ..., (x_(n-1),x_n) are graph edges of the graph and the x_i are distinct] (mathworld.wolfram.com/Path.html) and a sequence is an ordered set of mathematical objects. Consequently the answer is void and my assumed assumption is correct! $\endgroup$
    – Manfred Weis
    Jan 6, 2022 at 16:29
  • $\begingroup$ Maybe the OP is indeed wrong, but just stating it without a more detailed answer won't cut it. $\endgroup$
    – Alex M.
    Jan 6, 2022 at 20:23
  • 1
    $\begingroup$ @AlexM. Helsgaun's definition of a cycle that is found in th the linked paper on article page 120 (pdf: 2) is "A cycle is a set of edges $\lbrace (i_1,i_2),(i_2,i_3),\dots,(i_k,i_1)\rbrace$ with $i_p\ne i_q$ for $p\ne q$. That IMHO clearly proves that the PO is indeed right. It disappoints me a bit that the trollish answer was upvoted that much... $\endgroup$
    – Manfred Weis
    Jan 7, 2022 at 15:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.