Note on the Inverse Metric Traveling Salesman Problem Against the Minimum Spanning Tree Algorithm
Yerim Chung · Management Science and Financial Engineering · 2014
In this paper, we consider an interesting variant of the inverse minimum traveling salesman problem. Given an instance (G, w) of the minimum traveling salesman problem defined on a metric space, we fix a specified Hamiltonian cycle $HC_0$ . The task is then to adjust the edge cost vector w to w' so that the new cost vector w' satisfies the triangle inequality condition and $HC_0$ can be returned by the minimum spanning tree algorithm in the TSP-instance defined with w'. The objective is to minimize the total deviation between the original and the new cost vectors with respect to the $L_1$ -norm. We call this problem the inverse metric traveling salesman problem against the minimum spanning tree algorithm and show that it is closely related to the inverse metric spanning tree problem.