COMPUTATIONAL-COMPLEXITY OF A COST ALLOCATION APPROACH TO A FIXED COST SPANNING FOREST PROBLEM

被引:19
作者
GRANOT, D
GRANOT, F
机构
关键词
COST ALLOCATION; GRAPH OPTIMIZATION; FIXED COST; SPANNING FOREST; COOPERATIVE GAME APPROACH;
D O I
10.1287/moor.17.4.765
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We present a computational analysis of a game theoretic approach to a cost allocation problem arising from a graph optimization problem, referred to as the fixed cost spanning forest (FCSF) problem. The customers in the FCSF problem, represented by nodes in a graph G, are in need of service that can be produced at some facilities yet to be constructed. The cost allocation problem is concerned with the fair distribution of the cost of providing the service among customers. We formulate this cost allocation problem as a cooperative game, referred to as the FCSF.game. In general, the core of a FCSF game may be empty. However, for the case when G is a tree, it is shown that the core is not empty. Moreover, we prove that in this case core points can be generated in strongly polynomial time. We further provide a nonredundant characterization of the core of the FCSF game defined over a tree in the special case when all nodes are communities. This is shown to lead, in some instances, to a strongly polynomial algorithm for computing the nucleolus.
引用
收藏
页码:765 / 780
页数:16
相关论文
共 41 条
[21]   A cost allocation problem arising in hub-spoke network systems [J].
Matsubayashi, N ;
Umezawa, M ;
Masuda, Y ;
Nishino, H .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 160 (03) :821-838
[22]   A non-cooperative approach to the folk rule in minimum cost spanning tree problems [J].
Hernandez, Penelope ;
Peris, Josep E. ;
Vidal-Puga, Juan .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2023, 307 (02) :922-928
[23]   A new approach for cost allocation and reactive power pricing in a deregulated environment [J].
S. Hasanpour ;
R. Ghazi ;
M. H. Javidi .
Electrical Engineering, 2009, 91 :27-34
[24]   A cooperative game approach to cost allocation in a rapid-transit network [J].
Rosenthal, Edward C. .
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2017, 97 :64-77
[25]   A new approach for cost allocation and reactive power pricing in a deregulated environment [J].
Hasanpour, S. ;
Ghazi, R. ;
Javidi, M. H. .
ELECTRICAL ENGINEERING, 2009, 91 (01) :27-34
[26]   A new approach for determination and cost allocation of reserve in the restructured power systems [J].
Afshar, K. ;
Barati, M. M. .
ELECTRIC POWER SYSTEMS RESEARCH, 2013, 100 :25-33
[27]   Research on Cost Allocation Problem for Environment Equipments Choice Based on Cooperative Game [J].
Ma Zhisheng ;
Wang Mingchao .
GEOLOGY RESOURCE MANAGEMENT AND SUSTAINABLE DEVELOPMENT, 2010, :262-265
[28]   Estimation of cost allocation coefficients at the farm level using an entropy approach [J].
Fragoso, Rui ;
da Silva Carvalho, Maria Leonor .
JOURNAL OF APPLIED STATISTICS, 2013, 40 (09) :1893-1906
[29]   A vertex oriented approach to the equal remaining obligations rule for minimum cost spanning tree situations [J].
Barış Çiftçi ;
Stef Tijs .
TOP, 2009, 17 :440-453
[30]   A vertex oriented approach to the equal remaining obligations rule for minimum cost spanning tree situations [J].
Ciftci, Baris ;
Tijs, Stef .
TOP, 2009, 17 (02) :440-453