×

On the core of a traveling salesman cost allocation game. (English) Zbl 0675.90102

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.
Reviewer: N.Novikova

MSC:

91A12 Cooperative games
90C35 Programming involving graphs or networks
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland New York · Zbl 0483.05029
[2] Dirac, G. A., A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Society, 17, 85-92 (1962) · Zbl 0046.41001
[3] Dror, M., Cost allocation: The traveling salesman, bin-packing, and the knapsack, (Technical Report (1987), INRS-Telecommunications: INRS-Telecommunications Quebec, Canada) · Zbl 0711.90056
[4] Fonlupt, J.; Naddef, D., The traveling salesman problem in graphs with some excluded minors, (Technical Report 557 (1985), Université Scientifique et Medicale de Grenoble: Université Scientifique et Medicale de Grenoble France) · Zbl 0780.05034
[5] Granot, D., A generalized linear production model: A unifying model, Mathematical Programming, 34, 212-222 (1986) · Zbl 0604.90142
[6] Granot, D.; Huberman, G., Minimum cost spanning tree games, Mathematical Programming, 21, 1-18 (1981) · Zbl 0461.90099
[7] Granot, D.; Huberman, G., On the core and nucleolus of M.C.S.T. games, Mathematical Programming, 29, 323-347 (1984) · Zbl 0541.90099
[8] Megiddo, N., Cost allocation for Steiner trees, Networks, 8, 1-6 (1978) · Zbl 0378.90118
[9] Megiddo, N., Computational complexity and the game theory approach to cost allocation for a tree, Mathematics of Operations Research, 3, 189-196 (1978) · Zbl 0397.90111
[10] Potters, J. A.M.; Curiel, I. J.; Tijs, S. H., Traveling salesman games, (Technical Report (1987), Catholic University Nijmegen: Catholic University Nijmegen The Netherlands) · Zbl 0749.90094
[11] Tamir, A., On the core of network synthesis games, (Technical Report (1987), New York University: New York University New York) · Zbl 0722.90091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.