陈建二教授在计算机理论研究所小组讨论会作学术报告

发布时间:2020-04-24文章来源: 浏览次数:

2020年4月22日(星期三)上午9:00-10:30,计算机理论研究所在广州大学企业微信上召开了每周的小组讨论会。本次会议由长江学者陈建二教授作了题为“On Time Lower Bounds for Kernelization Algorithms”的学术报告。

报告中,陈建二教授首先介绍了核心化技术作为一种数据预处理技术可应用在大数据环境,满足普通计算机计算资源不足的需求。然后以著名的线覆盖问题为例研究核心化算法的时间下界。核心化算法时间下界目前在世界上还没有系统的研究,但在大数据计算的应用背景下,变得尤为重要。陈建二教授首先证明了比较简单的扇格线覆盖问题的核心化算法时间下界。通过代数计算树和有限集合覆盖理论证明了扇格线覆盖问题的核心化算法的时间复杂性至少是 因一般线覆盖问题难于扇格线覆盖问题,从而得到一般线覆盖问题核心化算法时间复杂性下界 的结果。最后陈建二教授与王捍贫教授及其他老师与学生就如何得到线覆盖问题核心化算法的紧下界,以及如何设计线覆盖问题的最优算法等问题进行了充分讨论,并希望小组成员可以参与后续研究。

计算机理论研究所的部分教师、博士生和硕士生聆听了本次报告,并且进行了热烈的讨论,大家深感获益良多。

 

关闭 打印责任编辑:戚佩玲