Approximate fair cost allocation in metric traveling salesman games

A traveling salesman game is a cooperative game G = (N, c(D)). Here N, the set of players is the set of cities (or the vertices of the complete graph) and CD is the characteristic function where D is the underlying cost matrix. For all S subset of C N, define c(D)(S) to be the cost of a minimum cost Hamiltonian tour through the vertices of S boolean OR {0} where 0 is not an element of N is called as the home city. Define Core(g) = {x is an element of R-N : x(N) = c(D)(N) and for all S subset of N, x(S) <= c(D)(S)} as the core of a traveling salesman game G. Okamoto [15] conjectured that for the traveling salesman game 9 = (N, c(D)) with D satisfying triangle inequality, the problem of testing whether Core(G) is empty or not is NP-hard. We prove that this conjecture is true. This result directly implies the NP-hardness for the general case when D is asymmetric. We also study approximate fair cost allocations for these games. For this, we introduce the cycle cover games and show that the core of a cycle cover game is non-empty by finding a fair cost allocation vector in polynomial time. For a traveling salesman game, let is an element of-Core(9) = {x is an element of R-N : x(N) >= c(D)(N) and for all S subset of N, x(S) <= epsilon (.) c(D)(S)} be an is an element of-approximate core, for a given epsilon > 1. By viewing an approximate fair cost allocation vector for this game as a sum of exact fair cost allocation vectors of several related cycle cover games, we provide a polynomial time algorithm demonstrating the non-emptiness of the log(2)(vertical bar N vertical bar - 1)-approximate core by exhibiting a vector in this approximate core for the asymmetric traveling salesman game. We also show that there exists an epsilon(0) > 1 such that it is NP-hard to decide whether is an element of(0)-Core(G) is empty or not.