Traveling salesman games with the Monge property

Several works have indicated the relationships between polynomially solvable combinatorial optimization problems and the core non-emptiness of cooperative games associated with them, and between intractable combinatorial optimization problems and the hardness of the problem to decide the core non-emptiness of the associated games. In this paper, we study the core of a traveling salesman game, which is associated with the traveling salesman problem. First, we show that in general the problem to test the core non-emptiness of a given traveling salesman game is N P-hard. This corresponds to the N P-hardness of the traveling salesman problem. Second, we show that the core of a traveling salesman game is non-empty if the distance matrix is a symmetric Monge matrix, and also that a traveling salesman game is submodular (or concave) if the distance matrix is a Kalmanson matrix. These correspond to the fact that the Monge property and the Kalmanson property are polynomially solvable special cases of the traveling salesman problem. (C) 2003 Elsevier B.V. All rights reserved.