07-31【张鹏】管楼1318吴文俊数学重点实验室组合图论系列讲座之141

时间:2019-07-26

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

报告人:张鹏 教授 (山东大学)

时间: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割问题当前已知最好的近似比。 

报告人概况:张鹏,山东大学App澳门新葡新京官方网站副教授。2007年7月于中科院App所取得博士学位,长期以来从事组合优化和近似算法的研究工作。在Algorithmica、ToCS、TCS、DAM等主流国际期刊,以及LATIN、ISAAC、COCOON等主流国际会议发表论文40多篇,其中第一编辑SCI论文13篇,通讯编辑SCI论文3篇。主持国家自然科学基金面上项目两项。
XML 地图 | Sitemap 地图