资源描述：
《A Hierarchical Clustering Approach to.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ProceedingsoftheTwenty-ThirdInternationalJointConferenceonArtificialIntelligenceC-Link:AHierarchicalClusteringApproachtoLarge-ScaleNear-OptimalCoalitionFormation∗AlessandroFarinellia,ManueleBicegoa,SarvapaliRamchurnb,MauroZucchelliaaComputerScienceDepartment,UniversityofVerona,<firstname.la
2、stname>@univr.itbSchoolofElectronicsandComputerScience,UniversityofSouthampton,sdr@ecs.soton.ac.ukAbstractTodate,anumberofapproachesemployedinthisdo-mainaimtosolvetheCSGproblemoptimally,rangingCoalitionformationisafundamentalapproachtofromMixed-IntegerprogrammingtoBranch-andBoundtech-multi
3、-agentcoordination.Inthispaperweaddressniques[Rahwanetal.,2009]throughDynamicProgrammingthespecificproblemofcoalitionstructuregener-(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,whilethisisasignificantimprovement,itcannotsettings.OurresultsshowthattheC-linkapproachclaimtosolveCSGprobleminpracticalapplications,suchperformsverywellagainstanoptimalbenchmarkas,forexample,co
7、llectivepurchasing,wherethousandsofbasedonMixed-IntegerProgramming,achievingagentsmightbeinvolved1.Incontrast,herewefocusonpro-solutionswhichareintheworstcaseabout80%vidinggood-enoughsolutions(near-optimal)usingheuristicoftheoptimal(inthesyntheticdata-set),and
