时间：7月18号上午九点
地点：经管学院（电教楼211会议室）
报告人：朱滨海教授
Topic：On Computing a Center Persistence Diagram
主题: 持续性图中心的求解计算
Abstract: Persistence diagram is a new tool from computational topology to capture the topological and geometric changes for large point clouds (or more complex objects). This talk first introduces the basics on persistence diagrams (e.g., the bottleneck distance between two diagrams). Then, we consider the center persistence diagram problem, i.e., one whose maximum bottleneck distance to m given diagrams is minimized . We show that, when m=2 diagrams are given, the problem is polynomially solvable. When m=3, we prove its NP-hardness (in fact, NP-hard to approximate within a factor of 2). Finally, we give a tight factor-2 approximation for the problem. No prior knowledge on topology is needed for this talk.
摘要：持久性图是一种新的工具，它从计算拓扑中捕捉大点云(或更复杂的对象)的拓扑和几何变化。本报告首先介绍了持久性图的基础知识(例如，两个图之间的瓶颈距离)。然后，我们考虑中心持久性图问题，即，其到m个给定图的最大瓶颈距离最小。我们证明，当m=2图给出时，问题是多项式可解的。当m=3时，我们证明了它的NP-hard(事实上，NP-hard在2的因子范围内难以近似)，最后给出了一个紧因子-2的近似解。本讲座不需要拓扑学的先验知识。
报告人简介：加拿大McGill大学获计算机科学博士学位。1994至1996年在美国新墨西哥州Los Alamos国家实验室完成博士后。2006年起任蒙大拿州立大学正教授。2009年获国家自然科学基金委海外杰出青年基金资助。研究领域为算法设计和分析，组合最优化，计算几何，参数计算。现已在国际期刊和学术会议上发表超过100篇学术论文（其中含顶级学术期刊及学术会议文章近20篇）。其设计的Jump-and-Walk算法已被很多著名的软件（如Triangle）所使用。现为Journal of Computers,Theoretical Computer Science, Journal of Combinatorial Optimization, International Journal of Computational Geometry and Applications等期刊的编委和客座编委。