ECCC-Report TR95-016https://eccc.weizmann.ac.il/report/1995/016Comments and Revisions published for TR95-016en-usFri, 17 Mar 1995 14:01:41 +0200
Paper TR95-016
| On approximately fair cost allocation in Euclidean TSP games |
U. Faigle,
S.P. Fekete,
W. HochstÃ¤ttler,
W. Kern
https://eccc.weizmann.ac.il/report/1995/016We 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.
Fri, 17 Mar 1995 14:01:41 +0200https://eccc.weizmann.ac.il/report/1995/016