报告题目：Lyapunov function approach for approximation algorithm design and analysis: with applications in continuous submodular maximization

报告时间：2023年6月1日 19:30

报告地点：腾讯会议707 374 518

报 告 人：杜东雷 教授

报告摘要：We propose a two-phase systematical framework for approximation algorithm design and analysis via Lyapunov function. The first phase consists of using Lyapunov function as an input and outputs a continuous-time approximation algorithm with a provable approximation ratio. The second phase then converts this continuous-time algorithm to a discrete-time algorithm with almost the same approximation ratio along with provable time complexity. One distinctive feature of our framework is that we only need to know the parametric form of the Lyapunov function whose complete specification will not be decided until the end of the first phase by maximizing the approximation ratio of the continuous-time algorithm. Some immediate benefits of the Lyapunov function approach include: (i) unifying many existing algorithms; (ii) providing a guideline to design and analyze new algorithms; and (iii) offering new perspectives to potentially improve existing algorithms. We use various submodular maximization problems as running examples to illustrate our framework.

报告人简介：杜东雷教授，曾任加拿大新布朗什维克大学商学院副院长，主要研究领域为组合优化、鲁棒优化、近似算法、社会网络分析、博弈论算法、供应链管理、选址问题及排序理论等。杜东雷教授科研成果发表在诸多国际一流学术期刊上，包括Operation Research，Algorithmic，SIAM Journal on Discrete Mathematics, European Journal of Operation Research，Omega等。