Indexed by:
Abstract:
Coalition formation is a key topic in multi-agent systems. To date, most work on this problem has concentrated on simple characteristic function games. However, this lacks the notion of tasks which makes it more difficult to apply it in many applications. Dang et showed that this problem was NP-hard and that the minimum number of coalition structures that need to be searched through in order to establish a solution within a bound from the optimal was (2(m+n-1)-1). Then Dang et presented an algorithm that takes a step further to search those task-based coalition structures whose biggest task-based coalition's cardinality is greater than or equal to [n(K - 1)/(K + 1)] in order to attain the bound K, which is the best result known so far. Against this background, this paper reports on a novel anytime algorithm based on cardinality structure that only have to take a step further to search those task-based coalition structures whose cardinality structure is in the CTCS(n, m, K*). Finally via contrast experiment, the algorithm reported in this paper is obviously better than that of Dang et al. (up to 10(19) times faster when n=60,m=40, K=3).
Keyword:
Reprint 's Address:
Email:
Version:
Source :
AGENT COMPUTING AND MULTI-AGENT SYSTEMS
ISSN: 0302-9743
Year: 2009
Volume: 5044
Page: 398-403
Language: English
0 . 4 0 2
JCR@2005
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: