Home>Results

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

[期刊论文]

An anytime coalition structure generation based on the grouping idea of cardinality structure

Share
Edit Delete 报错

author:

Li, S. (Li, S..) [1] | Hu, S. (Hu, S..) [2] | Shi, C. (Shi, C..) [3]

Indexed by:

Scopus PKU CSCD

Abstract:

Coalition formation is a key topic in multi-agent system. However, finding the optimal coalition structure is NP-complete. Sandholm and Larson et al. showed that it was necessary and sufficient to search the lowest two levels of the coalition structure graph in order to establish a worst-case bound k. How to do further search after the lowest two levels of the coalition structure graph is a problem which hasn't been resolved well for a long time. In actual problem such as task assignment, the different coalitions have the characteristics of the same cardinality and same value, or the value of two coalitions with the same cardinality differs a bit. This paper studies the problem about the optimal cardinality structure generation, analyzes the grouping thought of cardinality structures and presents a new anytime algorithm of coalition structure generation. The algorithm gives further search that can decrease bound to 2. After the minimal search, the complement search from the bottom to top in the process is also discussed that declines bound from 2 to 1. It is obviously better than Sandholm et al. and Dang et al.' s in the searching number of cardinality structure and coalition structure, or attaining bound, which is a important progress in the problem of coalition structure generation based on cardinality structure.

Keyword:

Anytime; Cardinality structure; Coalition structure; Grouping; Multi-agent system

Community:

  • [ 1 ] [Li, S.]Department of Electronic Information Engineering, Putian College, Putian, Fujian 351100, China
  • [ 2 ] [Hu, S.]Department of Computer Science and Technology, Fuzhou University, Fuzhou 350108, China
  • [ 3 ] [Shi, C.]Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

Reprint 's Address:

  • [Li, S.]Department of Electronic Information Engineering, Putian College, Putian, Fujian 351100, China

Show more details

Source :

Computer Research and Development

ISSN: 1000-1239

Year: 2011

Issue: 11

Volume: 48

Page: 2047-2054

Cited Count:

WoS CC Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:114/10115637
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