A note on the 5-person traveling salesman game

A note on the 5-person traveling salesman game

0.00 Avg rating0 Votes
Article ID: iaor19942326
Country: Germany
Volume: 38
Start Page Number: 131
End Page Number: 139
Publication Date: Sep 1993
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors:
Keywords: programming: travelling salesman
Abstract:

Let N={1,2,...,n} be a set of customers and G=(Nℝ{0},E) an undirected connected graph with non-negative edge lengths. 0 is the home location of a salesman who visits the customers in N. Each subset S⊆N can invite the salesman to visit its members only. The cost c(S) of coalition S is the length of a shortest tour that starts in 0, visits each customer in S at least once and returns to 0. The cooperative cost game defined in this way is called a (symmetric) traveling salesman game (TSG). The core of a TSG can be empty when ℝNℝ≥6 and it was proved that it always has a non-empty core when ℝNℝ•4. In this note it is proven that a TSG always has a non-empty core when ℝNℝ=5.

Reviews

Required fields are marked *. Your email address will not be published.