We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
An Abortion Based Search Method for Optimal Coalition Structure Generation.
- Authors
Narayan, Changder; Samir, Aknine; Animesh, Dutta
- Abstract
The Coalition Structure Generation (CSG) problem is a partitioning of a set of agents into exhaustive and disjoint subsets to maximize social welfare. This NP-complete problem arises in many practical scenarios. Prominent examples are included in the field of transportation, e-Commerce, distributed sensor networks, and others. The fastest exact algorithm to solve the CSG problem is ODP-IP, which is a hybrid version of two previously established algorithms, namely Improved Dynamic Programming (IDP) and IP. In this paper, we show that the ODP-IP algorithm performs many redundant operations. To improve ODP-IP, we propose a faster abortion mechanism to speed up IP's search. Our abortion mechanism decides at runtime which of the IP's operations are redundant to skip them. Then, we propose a modified version of IDP (named MIDP) and an improved version of IP (named IIP). Based on these two improved algorithms, we develop a hybrid version (MIDP-IIP) to solve the CSG problem. After a detailed description of the new algorithm MIDP-IIP, an experimental comparison is conducted against ODP-IP. Our analysis shows that MIDP-IIP performs fewer operations than ODP-IP. In addition, MIDP-IIP reduced significantly many problem instances running times (11–37%).
- Subjects
ABORTION; NP-complete problems; COALITIONS; DYNAMIC programming; SOCIAL services; SENSOR networks
- Publication
Group Decision & Negotiation, 2022, Vol 31, Issue 4, p747
- ISSN
0926-2644
- Publication type
Article
- DOI
10.1007/s10726-022-09781-2