Document Type

Article

Publication Date

1998

Publication Title

Journal of Applied Mathematics and Decision Sciences

Volume

2

Issue

2

First Page

177

Last Page

191

Keywords

Traveling salesman problem, Kalmanson matrix, polynomial algorithm.

Abstract

Two instances of the traveling salesman problem, on the same node set (1,2 n} but with different cost matrices C and C, are equivalent iff there exist {a, hi: -1, n} such that for any 1 _i, j _n, j, C(i, j) C(i,j) q-a -t-bj [7]. One ofthe well-solved special cases of the traveling salesman problem (TSP) is the convex-hull-and-line TSP. We extend the solution scheme for this class of TSP given in [9] to a more general class which is closed with respect to the above equivalence relation. The cost matrix in our general class is a certain composition of Kalmanson matrices. This gives a new, non-trivial solvable case of TSP.

Comments

This article was originally published in the Journal of Applied Mathematics and Decision Sciences, Hindawi Publishing Corporation.

Included in

Business Commons

Share

COinS