English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/132415
logo share SHARE   Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:

DC FieldValueLanguage
dc.contributor.authorBistaffa, Filippo-
dc.contributor.authorFarinelli, Alessandro-
dc.contributor.authorCerquides, Jesús-
dc.contributor.authorRodríguez-Aguilar, Juan Antonio-
dc.contributor.authorRamchurn, Sarvapali-
dc.identifierisbn: 978-163439131-3-
dc.identifier.citationProceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014; Paris; France; 5 May 2014 through 9 May 2014. Vol. 1, pp. 13-20, 2014-
dc.description.abstractWe consider the coalition structure generation (CSG) problem on synergy graphs, which arises in many practical applications where communication constraints, social or trust relationships must be taken into account when forming coalitions. We propose a novel representation of this problem based on the concept of edge contraction, and an innovative branch and bound approach (CFSS), which is particularly efficient when applied to a general class of characteristic functions. This new model provides a non-redundant partition of the search space, hence allowing an effective paralleli-sation. We evaluate CFSS on two benchmark functions, the edge sum with coordination cost and the collective energy purchasing functions, comparing its performance with the best algorithm for CSG on synergy graphs: DyCE. The latter approach is centralised and cannot be efficiently parallelised due to the exponential memory requirements in the number of agents, which limits its scalability (while CFSS memory requirements are only polynomial). Our results show that, when the graphs are very sparse, CFSS is 4 orders of magnitude faster than DyCE. Moreover, CFSS is the first approach to provide anytime approximate solutions with quality guarantees for very large systems (i.e., with more than 2700 agents). Copyright © 2014, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.-
dc.description.sponsorshipCerquides and Rodríguez-Aguilar are funded by projects COR (TIN2012-38876-C02-01), AT (CSD2007-0022), and the Generalitat of Catalunya grant 2009-SGR-1434. This work was supported by the EPSRC-Funded ORCHID Project EP/I011587/1-
dc.relation.isversionofPublisher's version-
dc.subjectCollective energy purchasing-
dc.subjectCoalition formation-
dc.titleAnytime coalition structure generation on synergy graphs-
dc.typecomunicación de congreso-
dc.description.versionPeer Reviewed-
dc.contributor.funderGeneralitat de Catalunya-
dc.contributor.funderMinisterio de Economía y Competitividad (España)-
Appears in Collections:(IIIA) Comunicaciones congresos
Files in This Item:
File Description SizeFormat 
PROC_AAMAS2014_13-20.null639,27 kBUnknownView/Open
Show simple item record

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