On approximately fair cost allocation in Euclidean TSP games

Ulrich Faigle, Sándor P. Fekete, Winfried Hochstättler, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

40 Citations (Scopus)
6 Downloads (Pure)


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α times its own cost, whereα 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α≤4/3. We also exhibit examples showing that this ratio cannot be improved below 4/3.
Original languageEnglish
Pages (from-to)29-37
Number of pages9
JournalOR Spectrum = OR Spektrum
Issue number1
Publication statusPublished - 1998


Dive into the research topics of 'On approximately fair cost allocation in Euclidean TSP games'. Together they form a unique fingerprint.

Cite this