主讲人：戴国伟
报告题目：顶点不相交最短路径的置信传播算法
报告时间：2024-05-14 14:30-17:30
报告地点：腾讯会议: 913-294-202
报告摘要：作为理论计算机科学与运筹学交叉领域中的一个基础问题，不相交路径问题自上世纪的70年代起便一直受到数学与计算机界的广泛关注。研究揭示：寻找两条不相交最短路径在无向图中多项式可解，而在有向图中则为NP完全问题。目前已设计出不相交路径问题的一系列高效算法。然而，不同于具有高效分布式算法的最短路径问题，不相交路径的计算中需要全局信息，因此难以设计其高效的分布式算法。置信传播作为一种分布式消息传递启发式算法框架，在人工智能中的概率图模型、信息论中的误差修正、机器学习中的数据聚类、离散优化中的可满足性等方面具有广泛的应用前景。 本报告主要介绍置信传播算法在有向图中寻找顶点不相交最短路径问题（VDSP）的最优解的性能分析，推导出解决VDSP的迭代消息传递更新规则，并证明了:对于规模为n的加权有向图，若最优解唯一且边权重是非负整数，则置信传播算法在O(n^2)次迭代内收敛到最优解。此外，对VDSP多源多汇的推广模型进行了扩展研究和探讨。
个人简介：戴国伟，江苏盐城人，华中师范大学理学博士学位。主要从事图优化与算法、图神经网络与深度学习、随机与不确定网络优化的研究。近年来研究课题主要集中在图优化问题的分布式消息传递算法。已在IEEE Transactions on Information Theory、Journal of Parallel and Distributed Computing、Journal of Global Optimization 等国际著名期刊发表学术论文20余篇。目前担任美国数学学会Mathematical Reviews特邀评论员；主持国家自然科学基金青年项目一项，江苏省自然科学基金青年项目一项；参与国家自然科学基金面上项目3项，国家专利发明2项。