On the core of a traveling salesman cost allocation game
type: Item
instance of: scholarly article
title: On the core of a traveling salesman cost allocation game
zbMATH Open document ID: 0675.90102
DOI: 10.1016/0167-6377(89)90030-8
author: Arie Tamir
published in: Operations Research Letters
publication date: 1989-01-01T00:00:00Z
review text: A traveling salesman game is considered. The aim is to allocate his trip cost among the customers. Stable allocations belong to the corresponding cooperative game core. The characteristic function for every coalition is given by the solution of the traveling salesman problem for these very customers. The emptiness of the core for hypohamiltonian graphs is proved. Three more graphs with empty core are shown. Sufficient conditions on a graph which ensure the nonemptiness of the core are given. They require that the graph contains no minor which is isomorphic to one of the three above graphs. If the graph satisfies these conditions it is possible to compute a core allocation by solving a linear program of polynomial dimensions.
Mathematics Subject Classification ID: 91A12
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4106649
zbMATH Keywords: cost allocation
zbMATH Keywords: traveling salesman game
zbMATH Keywords: trip cost
zbMATH Keywords: core
zbMATH Keywords: hypohamiltonian graphs
reviewed by: N. M. Novikova
MaRDI profile type: Publication
full work available at URL: 0167-6377(89)90030-8
OpenAlex ID: W1985531479
cites work: Q3941433
cites work: A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
cites work: Cost allocation: The traveling salesman, bin packing, and the knapsack
cites work: The traveling salesman problem in graphs with some excluded minors
cites work: A generalized linear production model: A unifying model
cites work: Minimum cost spanning tree games
cites work: On the core and nucleolus of minimum cost spanning tree games
cites work: Cost allocation for steiner trees
cites work: Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree
cites work: Traveling salesman games
cites work: On the core of network synthesis games
Recommended article: On the core of traveling salesman games
Recommended article: Core-based cost allocation in the cooperative traveling salesman problem
Recommended article: On the Core of Cost Allocation Games Defined on Location Problems
Recommended article: Approximately fair cost allocation in metric traveling salesman games
Recommended article: The traveling salesman game: An application of cost allocation in a gas and oil company
Recommended article: Approximation and Online Algorithms
Recommended article: Q4733704
Recommended article: Cost Allocation in Combinatorial Optimization Games
Recommended article: On the core of multiple longest traveling salesman games
Recommended article: Cost allocation in shortest path games
description: scientific article; zbMATH DE number 4106649