-
Siyue Liu: Approximately Packing Dijoins via Nowhere-Zero Flows
Speaker: () Time: 16:20-17:20 Beijing Time Dec 13, 2024 (Friday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Siyue Liu is a Ph.D. student in the Algorithms, Combinatorics, and Optimization program at the Tepper School of Business, Carnegie Mellon University. Her research focuses on combinatorial optimization and integer programming. She has published in Mathematical Programming […]
-
Bingkai Lin: Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Speaker: () Time: 16:20-17:20 Beijing Time Dec 2, 2024 (Monday) Venue: 518, Research Building 4 Abstract: Speaker Bio: 林冰凯，南京大学计算机学院教授，博士生导师。博士毕业于日本东京大学，硕士及本科毕业于上海交通大学ACM试点班。研究领域是理论计算机科学，具体领域是参数复杂性(Parameterized Complexity) 及近似算法 (Approximation Algorithms)。主要成果包括独自解决了参数复杂性领域基础性难题——k-BICLIQUE问题的参数复杂性;在图嵌入问题参数复杂性的二分猜想这一长达十多年的公开问题上取得重要进展；对经典NP-难优化问题集合覆盖问题取得首个以及当前最好的参数算法不可近似比；证明了指数时间假设蕴含参数不可近似假设，推动了参数PCP理论的发展。成果获得理论计算机国际一流会议STOC 2024与计算机科学图论领域重要国际会议WG 2017最佳论文奖。两篇单独作者论文分别获国际算法会议SODA 2015最佳论文奖和最佳学生论文奖以及欧洲理论计算机重要会议ICALP 2019最佳论文奖。
-
Yike Chen: An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies
Speaker: Yike Chen (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) November 15, 2024 (Friday) Venue: 518, Research Building 4 Abstract: The Stacker Crane Problem (SCP) is a variant of the Traveling Salesman Problem where a crane must traverse a graph with designated pairs of pickup and delivery points, moving […]
-
王艺源: 大规模离散优化问题求解算法
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. […]
-
Chunyu Luo: A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem
Speaker: Chunyu Luo (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) November 1, 2024 (Friday) Venue: 518, Research Building 4 Abstract: A $k$-defective clique of an undirected graph $G$ is a subset of its vertices that induces a nearly complete graph with a maximum of $k$ missing edges. The maximum […]
-
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 […]
-
Chao Xu: An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies
Speaker: () Time: 10:30-12:00 Beijing Time Oct 17, 2024 (Thursday) Venue: 计算所环保园1号楼524会议室腾讯会议号：605 5793 9921，密码：图灵机被提出的年份（4位）B站直播网址：https://live.bilibili.com/22528138 Abstract: Speaker Bio: 许超，电子科技大学计算机科学与工程学院副教授，博士生导师，算法与逻辑团队成员。许超主要从事组合优化和算法的基础研究，在SODA、Mathematical Programming、SICOMP，等组合优化和算法的国际顶级期刊/会议上发表多篇学术论文。现主持国家自然科学基金优秀青年（海外）项目。
-
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 […]