Traveling salesman games |
| |
Authors: | Jos A M Potters Imma J Curiel Stef H Tijs |
| |
Institution: | (1) Department of Mathematics, University of Nijmegen, Toernooiveld, 6525 ED Nijmegen, Netherlands;(2) Department of Mathematics and Statistics, University of Maryland, 21228 Baltimore County, Catonsville, MD, USA |
| |
Abstract: | In this paper we discuss the problem of how to divide the total cost of a round trip along several institutes among the institutes visited. We introduce two types of cooperative games—fixed-route traveling salesman games and traveling salesman games—as a tool to attack this problem. Under very mild conditions we prove that fixed-route traveling salesman games have non-empty cores if the fixed route is a solution of the classical traveling salesman problem. Core elements provide us with fair cost allocations. A traveling salesman game may have an empty core, even if the cost matrix satisfies the triangle inequality. In this paper we introduce a class of matrices defining TS-games with non-empty cores. |
| |
Keywords: | Primary 90D12 Secondary 90C08 |
本文献已被 SpringerLink 等数据库收录! |
|