I currently need to implement the algorithm discussed in Edge Elimination in TSP Instances by Hougardy and Schroeder (can be found at https://arxiv.org/abs/1402.7301)
I implemented Step 1 (of 3) which works fine but Step 2 is hard for me to figure out. The procedure can be found on page 10, Section 6.
For an edge $pq$ we consider two vertices $r$ and $s$ with all their incident edge pairs. The Close Point Elimination is used to reduce the number of possible edge pairs. The edge $pq$ can be eliminated either if no edge pair can be found for $r$ or $s$, or if all combinations of edge pairs satisfy the condition of the Main Edge Elimination Theorem.
I think I grasp the later part but how do I choose $r$ and $s$?
I first though about following procedure but it gave me wrong results ($V$ is the set of all edges and $E$ is the set of all edges):
- I ordered the 10 nearest vertices based on the middle point of the edge $pq$ (did this in Step 1)
- For the Close Point Elimination (page 5 Section 4), I chose a vertex $r$ and $s$ with the requirement that they are connected to vertex $p$ and $q$
- I use the algorithm given on page 6 Section 5 to check if a incident vertex of $r$ or $s$ is in $R:=\lbrace{x∈V|rx∈E∧pq∼rx\rbrace}$
- I apply Theorem 2 (page 5)
For point 3: I calculate $\delta_r$ then $L_p$ and $L_q$ (Page 6 Section 5 equation 10 and 11) after that I calculate $s_r$ so that I can apply Lemma 2 to get $R:=\lbrace{x∈V|rx∈E∧pq∼rx\rbrace}$
But what if $R$ is empty for either vertex $r$ or $s$? I can’t directly say that edge $pq$ is useless now.
I appreciate every bit help!