Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR95-016 | 2nd February 1995 00:00

On approximately fair cost allocation in Euclidean TSP games



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.

ISSN 1433-8092 | Imprint