TR95-016 Authors: U. Faigle, S.P. Fekete, W. HochstÃ¤ttler, W. Kern

Publication: 17th March 1995 14:01

Downloads: 802

Keywords:

We consider the problem of fair cost allocation for traveling

salesman games for which the triangle inequality holds. We

give examples showing that the core of such games may be

empty, even for the case of Euclidean distances. On the

positive side, we develop an LP-based allocation rule

guaranteeing that no coalition pays more than $\alpha$

times its own cost, where $\alpha$ is the ratio between

the optimal TSP-tour and the optimal value of its Held-Karp

relaxation (which is also known as the solution of the

"subtour polytope"). A well-known conjecture states that

$\alpha \leq 4/3$. We also exhibit examples showing that

this ratio cannot be improved below 4/3.