8月24日，2023年度国家自然科学基金青年基金资助项目结果公示， 本实验室刘鹏程博士的项目——最小权子图覆盖问题近似算法研究获批，这意味着实验室的科研实力和科技创新力更进一步。

本项目拟研究最小权子图覆盖问题及其相关问题的近似算法和学习算法。 该问题包含了顶点覆盖这样经典的组合优化问题，也包含了k路点覆盖问题、连通k子图覆盖问题等在网络安全领域新兴的应用问题。 虽然点覆盖问题已存在大量近似算法方面的研究，但更一般的子图覆盖问题的相关研究工作才刚刚展开，存在大量需要探索的空间。

本项目拟综合应用组合优化、图论、概率论、几何学、机器学习理论等工具研究 最小权子图覆盖问题的计算复杂性、设计高效可靠的近似算法、并从理论上得到尽可能紧的近似比； 考虑机器学习理论与近似算法理论的深度融合，利用机器学习得到性能更佳的近似算法，并得到有理论保证的机器学习算法。 力争在研究过程中提出新思路，开拓新方法，为组合优化及理论计算机科学的发展做出新贡献。