Abstract. 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 . We also exhibit examples showing that this ratio cannot be improved below .
Zusammenfassung: Wir betrachten die Aufgabe, die Kosten einer optimalen Traveling-Salesman-Tour fair unter den besuchten Knoten zu verteilen; insbesondere untersuchen wir den Fall, da die Kostenmatrix des zugrundeliegenden TSP-Problems die Dreiecksungleichung erfllt. Dazu wird das Modell von TSP-Spielen im Sinne der kooperativen Spieltheorie benutzt. Wir zeigen anhand eines Beispiels, da der Core eines solchen Spiels leer sein kann, selbst im Falle euklidischer Distanzen. Andererseits geben wir eine LP-basierte Verteilungsregel an, die garantiert, da keine Koalition mehr als das -fache ihrer eigenen Kosten bezahlen mu, wobei das Verhltnis zwischen den Kosten einer optimalen TSP-Tour und dem Optimum der Held-Karp-Relaxation ist, die auch als Lsung ber dem subtour polytope bekannt ist. Es wird allgemein vermutet, da . Abschlieend geben wir eine Klasse von Beispielen an, die beweist, da keine allgemeine Verteilungsregel fr das TSP-game ein generell besseres Verhltnis als zwischen der Belastung einer Koalition und ihren Kosten garantieren kann.