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

author:

Li, Shaofang (Li, Shaofang.) [1] | Hu, Shanli (Hu, Shanli.) [2] | Shi, Chunyi (Shi, Chunyi.) [3]

Indexed by:

EI 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:

Multi agent systems Structural optimization

Community:

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

Reprint 's Address:

Show more details

Related Keywords:

Source :

Computer Research and Development

ISSN: 1000-1239

CN: 11-1777/TP

Year: 2011

Issue: 11

Volume: 48

Page: 2047-2054

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 2

Online/Total:275/10028116
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