GRASP and path-relinking for Coalition Structure Generation
  In Artificial Intelligence with Coalition Structure Generation (CSG) one
refers to those cooperative complex problems that require to find an optimal
partition, maximising a social welfare, of a set of entities involved in a
system into exhaustive and disjoint coalitions. The solution of the CSG problem
finds applications in many fields such as Machine Learning (covering machines,
clustering), Data Mining (decision tree, discretization), Graph Theory, Natural
Language Processing (aggregation), Semantic Web (service composition), and
Bioinformatics. The problem of finding the optimal coalition structure is
NP-complete. In this paper we present a greedy adaptive search procedure
(GRASP) with path-relinking to efficiently search the space of coalition
structures. Experiments and comparisons to other algorithms prove the validity
of the proposed method in solving this hard combinatorial problem.
