0
$\begingroup$

Question:

given a complete symmetric graph $G(V,E)$ with $n$ vertices and edges $e_{ij}$ having weight $\omega_{ij}$, does there always exists a vector of vertex potentials $(\pi_1,\,\dots,\,\pi_n)$ that, when added to the weight of adjacent edges, guarantee that the minimum 1-tree of the Held-Karp lower bound resembles the edge-set of optimal tour, i.e. of the lightest Hamilton cycle of $G$.

I have scrutinized some related websites but couldn't find an explicit statement about the existence of such a vector, but only estimates, so a clarification would be of help.

$\endgroup$

1 Answer 1

0
$\begingroup$

Just found the answer in the 1969 paper THE TRAVELING-SALESMAN PROBLEM AND MINIMUM SPANNING TREES by Held and Karp; in which it is shown that it is not always possible to find the otimal solution to the TSP instance by systematic variation of the vertex potentials $\pi_i$ and provide a necessary and sufficient condition under which it is possible, namely if a certain wellknown linear program has an optimal solution in integers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy