学术讲座

大数据管理与分析方法研究北京市重点实验室（BDAI）研究生沙龙由人大高瓴人工智能智能学院与信息学院联合定期举行，本周BDAI重点实验室研讨会由信息学院孙亚辉老师和高瓴人工智能学院博士生任泽宇分别介绍各自课题组的工作。欢迎同学们积极参会。

汇报人：孙亚辉

时间：2021年10月27日 12：30-13：30

标题：点、边权重图中的点集合斯坦纳树算法研究

摘要：点集合斯坦纳树问题（the group Steiner tree problem）是图论中一个经典的NP-hard问题。在点和边均有非负权重的无向图中，给定一些点集，点集合斯坦纳树问题的目标是找一个最小权重的树覆盖所有的点集，即，对于每一点集，这个树中至少有一点在这个点集中 。求解点集合斯坦纳树问题是关系数据库中信息检索的关键步骤，在知识图谱、社交网络等多个应用场景下具有重要价值。然而，现有算法往往仅考虑边的权重，不考虑点的权重。迄今唯一考虑点的权重的算法具有指数时间复杂度，不具有实际使用价值。为弥补点权重场景下的点集合斯坦纳树算法的不足，本人在过去两年里研究了同时考虑点和边的权重的点集合斯坦纳树算法。

个人介绍：孙亚辉，哲学博士，于2021年9月入职中国人民大学，成为信息学院的一名讲师。其在哈尔滨工业大学获得了本科和硕士学位，并在澳大利亚墨尔本大学获得了哲学博士学位，研究方向为图论中的斯坦纳树问题。其目前的研究兴趣是图计算相关的数据挖掘算法，应用场景包括知识图谱、社交网络、城市网络、物联网等。近年来，其以第一作者兼通讯作者的身份在数据挖掘与计算机网络领域的顶级刊物Proceedings of the VLDB Endowment、IEEE/ACM Transactions on Networking上面发表了多篇文章。

汇报人：任泽宇

标题：Single Candidate Voting for Two-Winner in Euclidean Space

摘要：We study the 2-winner selection mechanism seeking to minimize the social cost. We assume candidates and voters are located in a Euclidean space. We are interested in strategy-proof mechanisms using single candidate voting rules. The quality of a mechanism is measured by its distortion, defined as the worst-case ratio between the social cost achieved by the mechanism and the optimal one. In our model, candidates’ locations are known to the mechanism and the ratio between the largest distance and the shortest distance among two candidates plays an important role in the distortion of mechanisms. When there are three candidates, the problem is largely solved by previous work. We mainly focus on the problem with at least four candidates. When voters and candidates are embedded in 1-dimensional space, we establish several lower bounds of the distortion. When voters and candidates are embedded in at least 3-dimensional space, we give a tight bound of the distortion.

个人介绍：任泽宇，博士二年级，研究方向：博弈论