标题：带权重标签割问题的近似算法
报告时间：2025年3月14日 （星期五） 09:30-11:00
报告地点：净月大街校区信息科学与技术学院楼304会议室
#腾讯会议：213-404-232
主讲人：张鹏
报告内容简介：
标签s-t割问题是一个得到广泛研究的著名问题。给一个图G，图上的每条边有一个标签，不同的边可以有相同的标签。再给源顶点s和目标顶点t，问题问如何选择最少数目的标签，使得在图上去掉具有这些标签的边能够将s和t断开。该问题当前已知最好近似比为O(n^(2/3))，其中n为图上顶点的数目。
但是，带权重的标签s-t割问题一直没有好的处理方法。在该问题中，每个标签有一个非负权重。问题问如何选择最小权重的若干标签，使得在图上去掉具有这些标签的边能够将s和t断开。
主讲人简介：
张鹏，山东大学软件学院教授、博导。研究方向为近似算法、组合优化和计算复杂性。中国计算机学会杰出会员，中国运筹学会数学规划分会常务理事。于2007年在中国科学院软件研究所取得博士学位。长期以来奋战在科研一线，以第一作者发表研究论文20余篇，共发表论文60余篇。论文主要发表在IANDC、IEEE-ACM TON、Algorithmica等顶级和主流国际期刊，以及LATIN，ISAAC，COCOON等主流国际会议上。主持国家自然科学基金项目四项，山东省自然科学基金项目一项，省部级教研项目两项。2023年4月，以独立作者在科学出版社出版本科生教材《最优化方法》。
