报告题目：标签割问题的近似算法和近似困难性 

报告人：张鹏 教授 （山东大学）

时间：7月31号上午 10：00-11：00，

地点： 1318

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

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

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