Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems (Q2639778)

Sensitivity analysis of a minimum Hamiltonian path (traveling salesman tour) H in an undirected weighted grah consists in finding how much the weight of each edge can be perturbed so that the optimality of H does not change. The maximum increment and decrement of the edge weight that preserve the optimality of H are called the edge tolerances with respect to H. This paper presents a method based on solving the sensitivity analysis for a minimum spanning tree (1-tree) for computing lower bounds of the edge tolerances, and gives some results of numerical experiments.