Technical Note—Data-Dependent Bounds for Heuristics to Find a Minimum Weight Hamiltonian Circuit

We consider the problem of finding a minimum weight Hamiltonian circuit in a weighted undirected graph. If the edge weights are non-negative and satisfy the triangle inequality, there are heuristics for this problem known to have data-independent bounds on their performance. We derive data-dependent bounds for these heuristics for arbitrary edge weight problems. Our approach leads to sharper bounds than the data-independent ones when the data is non-negative and satisfies the triangle inequality.