English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/157706
Share/Impact:
Statistics
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:
Title

Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems

AuthorsCruz-Mencia, Francisco ; Espinosa, Antonio; Moure, Juan Carlos; Cerquides, Jesús ; Rodríguez-Aguilar, Juan Antonio ; Svensson, Kim; Ramchurn, Sarvapali
KeywordsMulti agent systems
Multi-core systems
Set partitioning problem
Dynamic programming
Issue Date2017
PublisherJohn Wiley & Sons
CitationConcurrency Computation Practice and Experience 25: 4 (2017)
AbstractThe coalition structure generation problem is well known in the area of multi-agent systems. Its goal is to establish coalitions between agents while maximizing the global welfare. Among the existing different algorithms designed to solve the coalition structure generation problem, DP and IDP are the ones with smaller temporal complexity. After analyzing the operation of the dynamic programming and improved dynamic programming algorithms, we have identified which are the most frequent operations and propose an optimized method. In addition, we study and implement a method for dividing the work into different threads. To describe incremental improvements of the algorithm design, we first compare performance of an improved single central processing unit core version where we obtain speedups ranging from 7 × to 11 ×. Then, we describe the best resource use in a multi-thread optimized version where we obtain an additional 7.5 × speedup running in a 12-core machine. Copyright © 2016 John Wiley & Sons, Ltd.
URIhttp://hdl.handle.net/10261/157706
DOI10.1002/cpe.3969
Identifiersdoi: 10.1002/cpe.3969
issn: 15320626
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,38 kBAdobe PDFThumbnail
View/Open
Show full item record
Review this work
 

Related articles:


WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.