一种社交网络群组间信息推荐的有效方法

群组间信息推荐是社交网络中人们传递和分享资讯的重要途径,然而获取精确的最优推荐方案需要指数级时间开销.为此,本文提出一种有效算法EAOORS(Efficient Algorithm for Obtaining Optimal Recommendation Solution),将该指数级时间开销问题等价归约为EST(Extended Steiner Tree,扩展Steiner树)问题,并在多项式时间复杂度内快速获取近似最优推荐方案.理论分析和仿真实验表明,本文所提的算法具有有效性和实用性.     

社会网络中弱关系团队形成问题研究

随着在线社会网络的迅速发展,社会网络的团队形成问题逐渐成为研究热点。现有的社会网络中团队形成问题目标是寻找一个成员间沟通代价最小的团队。然而,实际应用中团队成员间的不紧密关系使得团队的观点多样化、多角度、无偏见,可以广泛应用于形成专家评审团队、大众评审团等。基于此需求,将社会学的弱关系概念引入团队形成问题中,提出了一种社会网络中弱关系团队形成问题。该问题旨在寻找成员间为弱关系,同时满足技能、经验值要求的一个团队,为NP-hard问题。提出了3类算法解决该问题,分别为贪心算法、精确算法、α-近似算法,每类算法有各自的特点与适用范围。利用ACM和DBLP两类真实的数据集进行实验,综合评估了各类算法的效率与求解质量,证明了提出算法的有效性。     

基于ε近似算法的空时多用户检测

阵列天线接收系统中,最优空时多用户检测器通过采用极大似然估计算法,可以逼近单用户的检测器性能,但由于其运算复杂度与用户数成指数关系而无实用价值。针对此把极大似然空时多用户检测问题转化为带约束的二次规划问题,从而把ε近似算法应用于空时多用户检测中。仿真实验表明,所提出的新算法表现出明显优于现有文献算法的良好性能。     

求解最大P-中心问题的一种近似算法

求解最大P-中心问题属于计算下模集函数最大值问题，该类问题在组合优化问题中具有非常重要的应用．为此，给出了求解具有简单约束的最大P-中心问题的一种局部搜索算法，并讨论了所给算法的性能保证．     

无线传感器网络不重复记录求和近似算法

针对现有的求和算法基本上都是对副本敏感的算法,提出一种对副本不敏感的求和近似算法FM-S。网络中各节点由FM-S和服从二项分布的随机数样本对节点记录进行哈希转换以填充一个长度为L的二进制求和序列,并且每个节点会把生成的序列转发给路由树中的父亲节点,根节点将接收到全网的求和序列,最终根据此序列可计算出网络中不重复记录求和的近似值。实验结果显示该算法是一种分布式、低功耗、容错性高、扩展性和健壮性强的聚集查询算法。     

动态网络中的高效多故障诊断技术

针对已有算法复杂度较高,不适用于规模较大网络的问题,将被管系统建立成动态贝叶斯模型,并提出一种能处理多故障的近似推理算法. 通过复杂度分析,证明该近似算法时间复杂度为多项式级,远远低于精确算法的时间复杂度下限,可以用于解决大规模动态网络的故障诊断问题. 实验结果证明,新算法在准确度方面虽然略低于精确算法,但执行效率上远远高于精确算法.     

带成组加工的二阶段柔性流水作业问题

本文仔细剖析混杂二阶段流水作业问题,其中第一阶段由m台同型机组成,第二阶段由一台批处理机M组成,并以最大完工时间Cmax为极小化目标函数.我们证明了该类问题除一种情况有多项式时间可解外,其余情况为(强)NP-hatd的.文中对所有(强)NP-hard情况均给出了近似算法并作了性能比分析.     

steiner树问题的近似算法

著名的Steiner树问题是,给定图G=(V、E),QV,在边集E上定义权函数f:E→Z~+,要求在图G上找一子树T=(Y,U),使得QY且 ∑_(c∈U)f(e)达到极小以后,我们称该问题为ST问题,R.M.Karp曾证明ST问题为NP-完全的,本文作者曾提出图上Steiner树问题:在图G=(V,E),QV上,要求一子树T=(Y,