On approximately fair cost allocation in Euclidean TSP games

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

Research output: Contribution to journalArticleAcademicpeer-review

35 Citations (Scopus)

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

Keywords

  • IR-85183
  • METIS-140791

Cite this