| Autor: |
Erlebach, Thomas, Persinao, Giuseppe, Bläser, M., Ram, L. Shankar |
| Zdroj: |
Approximation & Online Algorithms (9783540322078); 2006, p82-95, 14p |
| Abstrakt: |
A traveling salesman game is a cooperative game . 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 , define cD(S) to be the cost of a minimum cost Hamiltonian tour through the vertices of S∪ {0} where is called as the home city. Define Core as the core of a traveling salesman game . Okamoto [15] conjectured that for the traveling salesman game with D satisfying triangle inequality, the problem of testing whether Core 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 be an ε-approximate core, for a given ε > 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 log2(N-1)- approximate core by exhibiting a vector in this approximate core for the asymmetric traveling salesman game. We also show that there exists an ε0 > 1 such that it is NP-hard to decide whether ε0-Core is empty or not. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
