I’m having difficulty understanding the notion of Metric Excess described in the paper Edge Elimination in TSP Instances, by Stefan Hougardy and Rasmus T. Schroeder (at https://arxiv.org/abs/1402.7301).
I understand The Close Point Elimination Theorem that is described in section 4, on page 5 of the paper. Edge pq is useless if the length of edges
l(pr) + l(qr) + l(xy) < l(pq) + l(rx) + l(ry)
This appears to be a 3-opt version of Lemma 1, which is a 2-opt technique described in section 2, on page 3. It implies that edge pq is useless if the lengths of edges
l(px) + l(qr) < l(pq) + l(rx) and l(pr) + l(qx) < l(pq) + l(rx)
It also appears that The Close Point Elimination Theorem on edges pq, rx, ry finds more useless edges than using Lemma 1 on two separate edge pairs, pq rx and pq ry.
Now, the notion of Metric Excess is used in degenerate cases, where x = p, or y = q. The paper defines the Metric Excess as: The Metric Excess Mpq(z) of a vertex z with respect to an edge pq is
min max{ l(xz) + l(zp) – l(xp), l(yz) + l(zp) – l(yp), l(xz) + l(zq) – l(xq), l(yz) + l(zq) – l(yq) }
x,yN(z)\{p,q}
where vertex z is some point on edge pq, excluding vertices p and q.
Then, the paper jumps to Theorem 3 (Strong Close Point Elimination Theorem), section 4 on page 5. Let edges pq, pr, and rx be three edges of a TSP. If
l(xq) + l(rz) + l(zp) - Mpr(z) < l(pq) + l(rx),
then edges pq, pr, and rx are 3-incompatible.
It appears that you could use Lemma 1 on edges pq and rx to determine if edge pq is useless.
The questions below are for the degenerate case where y = q, with edges pq, qr, and rx.
- Where should vertex z be located on edge qr?
- Is the Metric Excess Mqr(z) of a vertex z with respect to an edge qr
s
min max{ l(xz) + l(zp) – l(xp), l(rz) + l(zp) – l(rp), l(xz) + l(zq) – l(xq), l(rz) + l(zq) – l(rq) }
x,yN(z)\{q,r}
Is this equation,
`l(xp) + l(rz) + l(zq) - Mqr(z) < l(pq) + l(rx)`
correct to determine if edges pq, qr, and rx are 3-incompatible?