北京科学与工程计算研究院学术报告之九十

报告人/Speaker: 张鹏(山东大学)


报告题目/Title: 求解稠密k子图问题的一个新的视角


时间/Date & Time: 2018年11月29日,16:30—17:30


地点/Location: 理科楼M843


报告摘要/Abstract:

给一个图G和正整数k,稠密k子图问题询问图G的一个k个顶点的子图,使得该子图上边的数目最多。稠密k子图问题是近似算法领域中一个著名的难解问题,经过长期的努力,该问题的可近似性上界和下界之间仍存在着巨大大的间隙。本报告介绍使用线性规划技术的稠密k子图问题的一种新的解法,对该问题提供了一个新的视角的审查。


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