1
$\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$
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

Not the answer you're looking for? Browse other questions tagged or ask your own question.