資源描述：
《A Hierarchical Clustering Approach to.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、ProceedingsoftheTwenty-ThirdInternationalJointConferenceonArtificialIntelligenceC-Link:AHierarchicalClusteringApproachtoLarge-ScaleNear-OptimalCoalitionFormation?AlessandroFarinellia,ManueleBicegoa,SarvapaliRamchurnb,MauroZucchelliaaComputerScienceDepartment,UniversityofVerona,
2、stname>@univr.itbSchoolofElectronicsandComputerScience,UniversityofSouthampton,sdr@ecs.soton.ac.ukAbstractTodate,anumberofapproachesemployedinthisdo-mainaimtosolvetheCSGproblemoptimally,rangingCoalitionformationisafundamentalapproachtofromMixed-IntegerprogrammingtoBranch-andBoundtech-multi
3、-agentcoordination.Inthispaperweaddressniques[Rahwanetal.,2009]throughDynamicProgrammingthespeci?cproblemofcoalitionstructuregener-(DP)[YunYeh,1986;RahwanandJennings,2008b].How-ation,andfocusonprovidinggood-enoughsolu-ever,noneofthesesolutionsarescalablegiventhattheinputtionsusinganovelheu
4、risticapproachthatisbasedtotheCSGproblemisexponentialinthenumberofagentsondataclusteringmethods.Inparticular,wepro-(O(nn)).Hencetheseoptimalapproachescanhandlerela-poseahierarchicalagglomerativeclusteringap-tivelysmallsetsofagents(i.e.,fewerthan30[Rahwanetal.,proach(C-Link),whichusesasimil
5、aritycriterion2009]).Recentapproaches[Voiceetal.,2012]exploitso-betweencoalitionsbasedonthegainthatthesys-cialrelationshipsamongtheagentstorestrictthesetoffea-temachievesiftwocoalitionsmerge.Weempir-siblecoalitions,andbysodoingtheycanoptimallysolveicallyevaluateC-Linkonasyntheticbenchmarkt
6、heCSGproblemforabout50agentsinsparsenetworks.data-setaswellasincollectiveenergypurchasingHowever,whilethisisasigni?cantimprovement,itcannotsettings.OurresultsshowthattheC-linkapproachclaimtosolveCSGprobleminpracticalapplications,suchperformsverywellagainstanoptimalbenchmarkas,forexample,co
7、llectivepurchasing,wherethousandsofbasedonMixed-IntegerProgramming,achievingagentsmightbeinvolved1.Incontrast,herewefocusonpro-solutionswhichareintheworstcaseabout80%vidinggood-enoughsolutions(near-optimal)usingheuristicoftheoptimal(inthesyntheticdata-set),and
