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

在科学理论及工程实践中存在大量的贪婪算法。然而，并非所有贪婪算法的好坏都能够在理论上得到成功的分析。现有的大多数分析贪婪近似算法的技巧都依赖于次模势函数,而如何设计与分析带非次模势函数的贪婪近似算法，则在很大程度上仍是一片亟待开垦的未知领域。本项目拟以概率分析等多种方法为工具，研究由不同应用领域（如无线传感器网络，社会网络等）提出的一些具有重要应用价值的NP-难组合优化问题，尤其是研究那些带非次模势函数的组合优化问题的贪婪近似算法。我们的研究目标是，通过对这些具体问题的研究，发展出基于非次模势函数的贪婪近似算法的新的理论和方法，从而进一步将其应用到更为一般的组合优化问题中。该项目的顺利完成将为组合优化及理论计算机领域的研究带来新的重要进展，同时也为应用领域的工作者如何设计更好的经验算法带来有益的启示。

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