基于非次模势函数的贪婪近似算法的设计与分析

该项目围绕无线传感器网络及社交网络中一些具有重要应用背景及理论价值的NP-难组合优化问题的近似算法设计展开研究，得到了一系列深入的研究成果，较好地完成了各项预定目标。项目取得的主要研究成果如下：针对无线传感网络中容错性虚拟骨干网的构造，我们设计出了第一个最小3-连通m控制支配集问题的常数倍近似算法；对最优k-sink放置问题设计出了基于贪婪算法的具有最好可能近似比的（2+ε）-近似算法（其中ε为任意小的常数）；对k-pah覆盖及加权最小控制集问题设计出了多项式时间近似方案（PTAS）；对社交网络中带时滞约束的影响力传播问题也在一定条件下给出了首个PTAS。这些近似算法一方面在理论上帮助我们更进一步理解这些组合优化问题的内在结构，另一方面也可望在实际中得到一定应用。通过对这些问题的近似算法研究，我们提炼出了一些新的近似算法设计方法，今后将进一步应用到更多的组合优化问题中。