Note on the Inverse Metric Traveling Salesman Problem Against the Minimum Spanning Tree Algorithm

Yerim Chung
May 2014
Management Science & Financial Engineering;May2014, Vol. 20 Issue 1, p17
Academic Journal
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 HC0. 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 HC0 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 L1-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.


Related Articles

  • Clustering, Randomness, and Regularity: Spatial Distributions and Human Performance on the Traveling Salesperson Problem and Minimum Spanning Tree Problem. Dry, Matthew J.; Preiss, Kym; Wagemans, Johan // Journal of Problem Solving;Winter2012, Vol. 4 Issue 1, p1 

    We investigated human performance on the Euclidean Traveling Salesperson Problem (TSP) and Euclidean Minimum Spanning Tree Problem (MST-P) in regards to a factor that has previously received little attention within the literature: the spatial distributions of TSP and MST-P stimuli. First, we...

  • Comparison of Heuristics for Resolving the Traveling Salesman Problem with Information Technology. Wei Gong; Mei Li // Advanced Materials Research;2014, Issue 886, p593 

    Traveling Salesman Problem (Min TSP) is contained in the problem class NPO. It is NP-hard, means there is no efficient way to solve it. People have tried many kinds of algorithms with information technology. Thus in this paper we compare four heuristics, they are nearest neighbor, random...

  • A NETWORK BRANCH AND BOUND APPROACH FOR THE TRAVELING SALESMAN MODEL. Munapo, Elias // South African Journal of Economic & Management Sciences;2013, Vol. 16 Issue 1, p52 

    This paper presents a network branch and bound approach for solving the traveling salesman problem. The problem is broken into sub-problems, each of which is solved as a minimum spanning tree model. This is easier to solve than either the linear programming-based or assignment models.

  • Some Applications of Spanning Trees in Complete and Complete Bipartite Graphs. Daoud, S. N. // American Journal of Applied Sciences;Apr2012, Vol. 9 Issue 4, p584 

    Problem statement: The number of spanning trees Ï„(G) in graphs (networks) is an important invariant, it is also an important measure of reliability of a network. Approach: Using linear algebra and matrix analysis techniques to evaluate the associated determinants. Results: In this study we...

  • EDITORIAL. Ruiz-Vanoye, Jorge A. // International Journal of Combinatorial Optimization Problems & I;Sep-Dec2014, Vol. 5 Issue 3, p1 

    An introduction to the journal is presented in which the editor discusses various reports published within the issue including an algorithm to solve the traveling salesman problem (TSP) adding three aspects of time, the desirable characteristics that must contain the software repositories for...

  • On the Generalized Network Design Problems. Pop, P.C. // Carpathian Journal of Electronic & Computer Engineering;2010, Vol. 3 Issue 1, p103 

    The aim of this paper is to present a survey on some of the most important generalized network design problems: the generalized minimum spanning tree problem, the generalized traveling salesman problem and the generalized vehicle routing problem.

  • Fast Algorithms for Geometric Traveling Salesman Problems. Bentley, Jon Jouis // ORSA Journal on Computing;Fall92, Vol. 4 Issue 4, p387 

    This paper describes efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets. We describe implementations of a dozen starting heuristics (including Nearest Neighbor and Farthest Insertion) and three local optimizations (including 2-Opt and 3-Opt)....

  • Multi-depot Multiple TSP: a polyhedral study and computational results. Benavent, Enrique; Martínez, Antonio // Annals of Operations Research;Aug2013, Vol. 207 Issue 1, p7 

    We study the Multi-Depot Multiple Traveling Salesman Problem (MDMTSP), which is a variant of the very well-known Traveling Salesman Problem (TSP). In the MDMTSP an unlimited number of salesmen have to visit a set of customers using routes that can be based on a subset of available depots. The...

  • The Inverse Spanning Tree of a Fuzzy Graph Based on Credibility Measure. Jian Zhou; Qina Wang; Xiang Zhang // Journal of Communications;Sep2013, Vol. 8 Issue 9, p566 

    An inverse spanning tree problem is to make the least modification on the edge weights such that a predetermined spanning tree is a minimum spanning tree. In this paper, based on the notion of fuzzy α-minimum spanning tree, the inverse spanning tree problem with fuzzy edge weights is...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics