Home>Results

  • Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

[期刊论文]

Anytime coalition structure generation algorithm based on cardinality structure

Share
Edit Delete 报错

author:

Su, S. (Su, S..) [1] | Hu, S. (Hu, S..) [2] | Zheng, S. (Zheng, S..) [3] | Unfold

Indexed by:

Scopus PKU CSCD

Abstract:

Coalition formation is a key topic in multi-agent systems. One may prefer a coalition structure that maximizes the sum of the values of the coalitions, but often the number of coalition structures is too large to allow exhaustive search for the optimal one. Furthermore, finding the optimal coalition structure is NP-hard and even finding a sub-optimal solution requires searching an exponential number of solutions. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? Sandholm et al. show that it suffices to search the lowest two levels of the coalition structure graph in order to establish a worst-case bound Kin). Dang et al. present an algorithm which is obviously faster than that of Sandholm et al, which is the best result known so far. Against this background, the relations among coalition structures are analyzed in depth and a novel anytime algorithm based on cardinality structure is presented, which only has to take a step further and search those coalition structures whose cardinality structure is in the CCS (n, b). Consequently, the algorithms reported are obviously better than that of Sandholm et al. (up to 1035 times faster when n=100, K=2) and Dang et al. (up to 1018 times faster when n=l00, K=3).

Keyword:

Anytime algorithm; Cardinality structure; Characteristic function; Coalition formation; Coalition structure generation; Multi-agent system

Community:

  • [ 1 ] [Su, S.]Department of Computer Science and Technology, Fuzhou University, Fuzhou 350002, China
  • [ 2 ] [Hu, S.]Department of Computer Science and Technology, Fuzhou University, Fuzhou 350002, China
  • [ 3 ] [Zheng, S.]Department of Computer Science and Technology, Fuzhou University, Fuzhou 350002, China
  • [ 4 ] [Lin, C.]Department of Computer Science and Technology, Fuzhou University, Fuzhou 350002, China
  • [ 5 ] [Luo, J.]Department of Computer Science and Technology, Fuzhou University, Fuzhou 350002, China

Reprint 's Address:

  • [Su, S.]Department of Computer Science and Technology, Fuzhou University, Fuzhou 350002, China

Show more details

Source :

Computer Research and Development

ISSN: 1000-1239

Year: 2008

Issue: 10

Volume: 45

Page: 1756-1762

Cited Count:

WoS CC Cited Count:

30 Days PV: 1

Affiliated Colleges:

Online/Total:155/10142265
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1