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

关键词：社交网络 信息推荐 近似算法 性能评估 

单位：同济大学计算机科学与工程系 上海201804 同济大学嵌入式系统与服务计算教育部重点实验室 上海201804 上海师范大学信息与机电工程学院 上海200234