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.


$$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.


  • 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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.