报告题目：标签s-t割问题的一个简单且好的近似算法

报告摘要：标签s-t割问题是在信息安全和计算机网络等领域中提出的一个组合优化问题。给一个图，边上有标签，该问题询问最少数目的标签，使得在图上把具有这些标签的边去掉后，能够将给定的源点s和目标点t断开。容易看出，标签s-t割问题是经典的最小s-t割问题的推广。

在本报告中，我们给出标签s-t割问题的两个纯组合算法。这两个算法的近似比分别为O(m^1/2)和O(n^2/3)，其中m和n分别为图上的边数和点数。这是标签s-t割问题当前已知最好的近似比。

报告时间：2017年3月27日（周一）下午15:45-16:30

报告地点：长清湖校区C区236

欢迎老师和同学参加！

报告人简介：张鹏，山东大学计算机学院副教授。2007年7月于中科院软件所取得博士学位。长期以来从事组合优化和近似算法的研究。在Algorithmica、ToCS、TCS、DAM等主流国际期刊，以及LATIN、ISAAC、COCOON等主流国际会议发表论文40多篇，其中以第一作者、通讯作者发表SCI索引论文14篇。主持国家自然科学基金面上项目两项。