-
王艺源: 大规模离散优化问题求解算法
Speaker: 王艺源 (Northeast Normal University) Time: 16:20-17:20 Beijing Time Nov 12, 2024 (Tuesday) Venue: 518, Research Building 4 Abstract: 大规模离散优化问题在许多实际应用中扮演着至关重要的角色，涉及物流、交通、资源分配、网络设计等多个领域。这类问题的复杂性源于其决策变量的离散性，通常需要在大量可能的解中寻找最优解。随着数据规模的不断增长和应用需求的日益复杂，传统的求解方法面临着效率和准确性的挑战。本次报告首先介绍求解算法效率的几种策略，包括克服循环搜索、基于变量依赖的预处理过程以及基于问题结构信息的启发式策略。之后，报告将重点围绕两个重要问题的求解：伪布尔优化问题和图同构问题。在伪布尔优化问题的研究中，提出了一种有效的局部搜索框架，显著提升了解的质量和求解的速度。针对图同构问题，提出了一种精确算法，提出了五个关键策略，包括更强的约束传播以简化顶点匹配域，引入结合点度数和解密度的匹配排序方法，以及自适应的约束传播机制。此外，为了更高效地求解大规模实例，提出了增强的边约束方法和域限制策略。实验结果表明，PathLAD+的性能显著优于当前多个最先进的精确算法。 Speaker Bio: 王艺源，男，东北师范大学信息科学与技术学院副教授，博士生导师，中国人工智能学会智能服务专委会委员，中国计算机学会理论计算机科学专委会委员，国际期刊IEEE-TLT专刊编委。2017年于吉林大学计算机科学与技术学院获得工学博士学位。2020年获得吉林省青年人才托举计划。主要从事人工智能、算法设计及其应用、逻辑推理、优化求解等方向研究，特别关注大规模组合优化问题求解等。主持并参与多项国家自然基金，在AIJ、JAIR、EJOR、AAAI、IJCAI、CP等上发表学术论文40余篇，其中以第一作者或通讯作者发表计算机学会推荐A类论文10余篇，并多次受邀担任IJCAI、AAAI等会议程序委员会委员。2022年国际MaxSAT比赛中包揽了完备组加权赛道和非加权赛道的冠军和亚军；2024年国际PBO比赛中获得两个赛道第一名，一个赛道第二名以及两个赛道第三名。
-
Bainian Hao: Inefficiency of the Pure Nash Equilibria in Structured Congestion Games
Speaker: Bainian Hao (University of Wisconsin-Madison) Time: 16:20-17:20 Beijing Time Nov 8, 2024 (Friday) Venue: 518, Research Building 4 Abstract: Congestion games are commonly used to model problems in large-scale networks and represent a simple, yet powerful paradigm for selfish resource sharing. These games belong to the larger class of potential games where the pure Nash equilibria is…
-
Yiding Feng: Beyond Regularity: Simple versus Optimal Mechanisms, Revisited
Speaker: () Time: 10:00-11:00 Beijing Time Nov 6, 2024 (Wednesday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Yiding Feng is an assistant professor at HKUST IEDA. Previously, he worked as a principal researcher at the University of Chicago Booth School of Business, and postdoctoral researcher at Microsoft Research New England. He received his Ph.D.…
-
Lev D. Beklemishev: Provability and computability
Speaker: Lev D. Beklemishev (Moskow State University) Time: 16:20-17:20 Beijing Time October 18, 2024 (Friday) Venue: 518, Research Building 4 Abstract: In this lecture we will give an introduction to the theory of computations and proofs. We will start with classical results such as decidable and undecidable problems and the Gödel incompleteness theorems. Then we…
-
Markus Lohrey: Selected topics in streaming algorithms
Speaker: () Time: 18:00-19:30 Beijing Time Sept 23, 2024 (Monday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Professor Markus Lohrey, Head of Theoretical Computer Science Group, The University of Siegen, Germany. His research interests are Decidability and complexity of problems in automata theory and algebra, Combinatorial Group theory, data compression, Logic in computer science…
-
Qi Shi: Responsibility and Norms in Multiagent Systems
-
Weili (Lily) Wu: The Art of Big Data: Accomplishments and Research Needs
Speaker: () Time: 11:00-12:00 (Time in Beijing) June 11, 2024 (Tuesday) Venue: 518 Abstract: Speaker Bio: Dr. Weili (Lily) Wu received her MS and PhD degrees in computer science both from University of Minnesota, in 1998 and 2002 respectively. She is currently a full professor and a lab director of the Data Communication and Data…
-
Boting Yang: On the One-Visibility Cops and Robber Game
Speaker: Boting Yang (The University of Regina) Time: 16:20-17:20 (Time in Beijing) May 30, 2024 (Thursday) Venue: 518, Research Building 4 Abstract: In this talk, we consider the one-visibility cops and robber game. The one-visibility cops and robber game is a variation of the classic cops and robber game, where one-visibility means that the information…
-
Qingyun Chen: Survivable Network Design Revisited: Group-Connectivity
Speaker: Qingyun Chen (University of California, Merced) Time: 10:00-11:00 (Time in Beijing) May 14, 2024 (Tuesday) Venue: B1-104，Main building Abstract: In the classical survivable network design problem (SNDP), we are given an undirected graph with costs on edges and a connectivity requirement for each pair of vertices. The goal is to find a minimum-cost subgraph…
-
Andre Nies: Prime numbers, factorisation, and algorithms
Speaker: Andre Nies (The University of Auckland) Time: 16:20-17:20 (Time in Beijing) April 19, 2024 (Friday) Venue: 518, Research Building 4 Abstract: Euclid in around 300 BC proved that the sequence of prime numbers is infinite. This sequence starts 2,3,5,7,11, 13, …; the largest currently known prime number is obtained by raising 2 to the…