ISSN:
1436-6304
Keywords:
Key words:Cooperative game, core, cost allocation, traveling salesman, Held-Karp bound
;
Schlüsselwörter: Kooperative Spiele, Core, Kostenallokation, Traveling Salesman, Held-Karp Schranke.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
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 erfüllt. 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 $\alpha$ -fache ihrer eigenen Kosten bezahlen muß, wobei $\alpha$ das Verhältnis zwischen den Kosten einer optimalen TSP-Tour und dem Optimum der Held-Karp-Relaxation ist, die auch als Lösung über dem “subtour polytope” bekannt ist. Es wird allgemein vermutet, daß $\alpha\leq \frac{4}{3}$ . Abschließend geben wir eine Klasse von Beispielen an, die beweist, daß keine allgemeine Verteilungsregel für das TSP-game ein generell besseres Verhältnis als $4 \over 3$ zwischen der Belastung einer Koalition und ihren Kosten garantieren kann.
Notes:
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 $\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\leq \frac{4}{3}$ . We also exhibit examples showing that this ratio cannot be improved below $\frac{4}{3}$ .
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s002910050049
Permalink