2011/03/06 by Nicola Di Mauro, Di Mauro, Nicola, Teresa M. A. Basile +5
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Artificial Intelligence (cs.AI) #Auction Theory and Applications #FOS: Computer and information sciences #Game Theory and Voting Systems #Logic, Reasoning, and Knowledge #cs.AI
paper · pdf · doi:10.48550/arxiv.1103.1157
openalex publication_date 2011/03/06 · arxiv created 2011/03/09 · arxiv updated 2011/03/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.