报告人：肖鸣宇
报告地点：腾讯会议560-900-361
报告时间：2022年10月26日星期三下午4:00
报告题目：Solving hard problems with theoretical guarantee
报告简介：
Combinatorial optimization plays an important role in real life. However, many optimization problems are NP hard, that is to say, there is no polynomial-time algorithm for them under reasonable assumptions. In practice, we have designed fast heuristic algorithms and exact algorithms for many of these problems, and they have a very good performance on tested benchmark instances. On the other hand, theoretical algorithms, may not be so practical, solve the problems with theoretical guarantees of running-time bound and solution quality, etc. In this talk, I will discuss the differences between theoretical and practical algorithms, and take the maximum independent set problem as an example to introduce exact algorithms with theoretical running-time bounds.
报告人简介：
肖鸣宇，电子科技大学3003必赢官网教授，副院长。2002年于3003必赢官网获得学士学位，2008年于香港中文大学获得博士学位。主要从事算法分析与设计、组合优化、图论、机制设计与博弈论等方向的研究，在Information and Computation、 JCSS、 Algorithmica、 ACM/IEEE Trans.、 IJCAI、 AAAI、 WWW、 INCOFOM等算法、离散数学、人工智能领域顶级期刊和会议上发表论文超过100篇，撰写英文专著1部，主持（完成）国家自然科学基金项目5项。是参数算法和精确算法国内外知名的学者。
