# Name for a Lower Bound on the Length of General TSPs and ATSPs

Let $$G\left(\ V,\ E=V\times V\setminus\lbrace(v_i,v_i)\rbrace,\ \Omega: E\ni e_{ij}\mapsto\omega_{ij}\in\mathbb{R}\right)$$ be a(n) (A)TSP instance.

Then

$$2*\ell(T_{\mathrm{opt}})\quad\ge\quad\sum_{v\in V}{\ \min_{(u,w)}\ \omega_{uv}+\omega_{vw}}$$

is a lower bound that can be calculated in $$\Theta(n^2)$$ time for TSPs time whereas for ATSPs I assume it might be $$O(n^2\log(n))$$ when utilizing adjacency lists that are sorted according to ascending edgeweights.

Questions:

• is there already a name for the described lower bound?
• are there online resources that discuss properties of that bound with regard to TSPs and ATSPs?

Remark: in practical TSP calculations one would of course take the maximum of other known lower bounds (most prominently the Held Karp bound) and the lower bound desribed above; that would guarantee that one gets the best of two worlds.