On approximately fair cost allocation in Euclidean TSP games

Faigle, Ulrich and Fekete, Sandor P. and Hochstättler, Winfried and Kern, Walter (1998) On approximately fair cost allocation in Euclidean TSP games.
Published in: OR Spektrum Vol. 20 (1). pp. 29-37.


We consider the problem of allocating the cost of an optimal traveling salesman tour in a fair way among the nodes visited; in particular, we focus on the case where the distance matrix of the underlying TSP problem satisfies the triangle inequality. We thereby use the model of TSP games in the sense of cooperative game theory. We give examples showing that the core of such games may be empty, even for the case of Euclidean distances. On the positive, 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 over the ''subtour polytope''. A well known conjecture states that alpha<=4/3. We also exhibit examples showing that this ratio cannot be improved below 4/3.

Download: [img] Postscript - Preprinted Version
Download (529kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr93-137
Depositing User: Prof. Dr. Ulrich Faigle
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 15:22
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/137