Cost allocation in the Chinese postman problem |
| |
| Institution: | 1. CentER and Department of Econometrics, Tilburg University, P.O. Box 90153, 5000 LE Tilburg, The Netherlands;2. Department of Quantitative Economics, University of Limburg, P.O. Box 616, 6200 MD Maastricht, The Netherlands;1. Institute of Physics, University of Silesia, Uniwersytecka 4, 40-007 Katowice, Poland;2. Institute of Physics, Pedagogical University, Podchorazych 2, 30-084 Krakow, Poland;1. Universitat d’Alacant, Mètodes Quantitatius i Teoria Econòmica and IUDESP, 03080 Alacant, Spain;2. Universitat Rovira i Virgili, Departament d’Economia and CREIP, Av.Universitat 1, 43204 Reus, Spain;1. School of Software, Dalian University of Technology, Dalian 116620, China;2. China Center for Industrial Security Research, Beijing Jiaotong University, Beijing 100044, China;1. National Agency for New Technologies, Energy and Sustainable Economic Development (ENEA), Frascati, Italy;2. Fusion for Energy (F4E) Broader Fusion Development Department, Garching, Germany;3. Japan Atomic Energy Agency (JAEA), Naka Fusion Institute, Mukouyama, Naka-si, Ibaraki-ken, Japan;4. OCEM Energy Technology, Valsamoggia, Italy;1. College of Information Technology, Shanghai Ocean University, Shanghai 201306, China;2. Department of Mathematics, East China University of Science and Technology, Shanghai 200237, China;3. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China;1. Stanford University, Department of Electrical Engineering, Stanford, CA 94305, United States;2. Stanford University, Department of Mathematics and Statistics, Sequoia Hall, 390 Serra Mall, Stanford, CA 94305-4065, United States;3. University of California, San Diego, Department of Mathematics, 9500 Gilman Drive #404, La Jolla, CA 92093, United States;4. Center for Communications Research, Princeton, NJ 08540, United States |
| |
| Abstract: | This paper considers a cost allocation problem that arises from a delivery problem associated with the Chinese postman problem (CPP). A delivery problem is described by a connected undirected graph in which each edge belongs to a different player, a cost function on the edges of this graph and a fixed vertex which is referred to as the post office. Assume that the post office is providing some service to the players. The nature of this service, which can be thought of as mail delivery, requires that a server will travel along the edges of the graph and returns to the post office. The cost allocation problem is concerned with the cost of providing the service to all players. A specific cost allocation rule is introduced and characterized. Further, the class of delivery problems gives rise to a new class of cooperative combinatorial optimization games called delivery games. It is shown that the outcome of the allocation rule with respect to a bridge-connected Euler graph is a core element of the corresponding delivery game. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
