Journal of Software:2011.22(5):938-950

(烟台大学 计算机科学与技术学院,山东 烟台 264005)
O(2.983n) Time Complexity Algorithm for Optimal Coalition Structure Generation
LIU Jing-Lei,ZHANG Wei,TONG Xiang-Rong,ZHANG Zhen-Rong
(School of Computer Science and Technology, Yantai University, Yantai 264005, China)
Chart / table
Similar Articles
Article :Browse 4172   Download 3358
Received:April 05, 2009    Revised:January 05, 2010
> 中文摘要: 首先,在有限整数集上建立有效拆分关系,在联盟集上建立有效二部分解关系,并设计了一种EOCS (effective optimal coalition structure)算法.该算法采用自底向上方式,只对具有有效二部分解关系的联盟进行二部分解来求联盟的优值,从而降低了二部分解的数量.随后,利用函数的克林闭包特性证明了EOCS算法的正确性,利用积分极限定理证明了EOCS 算法时间复杂度的下界是Ω(2.818n),用时间序列分析方法求出了EOCS 算法的上界是
Abstract:First, this paper establishes an effective partition relationship in the finite integer set and an effective splitting relationship in the coalition set, and devises an EOCS (effective optimal coalition structure) algorithm, which only evaluates bipartite effective splittings of coalition to find the optimal value from bottom to top, so it decreases the number of bipartite splitting. Secondly, the correctness of the EOCS algorithm is proved based on the Kleene closure function. Moreover, this paper proves that the EOCS lower bound is Ω(2.818n) by the integration limit theorem, and discovers that the EOCS upper bound is O(2.983n) by the time serial analysis technique. Finally, this paper compares the EOCS algorithm with other algorithms to point out that the EOCS algorithm can find optimal coalition structure in O(2.983n) time whether the coalition values meet which probability distributions or not. The DP (dynamic programming) algorithm and the IDP (improved dynamic programming) algorithm proposed by Rothkopf and Rahwan can find an optimal solution in O(3n). The EOCS algorithm’s design, correctness proof, and time complexity analysis are all improvements of Rothkopf and Rahwan’s related work.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(60496323); 山东省教育厅科技计划(J07JYJ24) 国家自然科学基金(60496323); 山东省教育厅科技计划(J07JYJ24)
Foundation items:
Reference text:


LIU Jing-Lei,ZHANG Wei,TONG Xiang-Rong,ZHANG Zhen-Rong.O(2.983n) Time Complexity Algorithm for Optimal Coalition Structure Generation.Journal of Software,2011,22(5):938-950