关于点集覆盖问题近似算法及其相关问题的研究

点集覆盖问题是一个经典的NP-完全问题，除非NP=P，点集覆盖问题没有多项式算法，人们只能寻找它的近似算法。目前，该问题最好的近似算法几乎仍然是用极大匹配所给出的方法，它的界为2。对于点集覆盖问题，是否存在严格小于2的界的近似算法？- - 是组合优化近似算法领域中的一个十分重要的open问题。尽管有很多的知名学者都曾致力于该问题的研究，但2的界一直没有能完全突破。从1999年我们开始接触和研究该问题，相关的研究已经持续了多年。结合数值试验，我们发现通过添加奇数圈约束，考虑点集覆盖问题扩充的线性规划松弛问题，有可能使问题获得突破。我们已经获得了一些初步的研究成果。本项目将进一步研究如何加强点集覆盖问题的扩充的线性规划松弛问题，以及如何利用松弛问题的解的信息，构造更好的近似算法，解决或部分解决点集覆盖问题。同时，本项目也将研究一些与点集覆盖问题相关的问题，如57度Moore图的存在性问题等。

本项目研究点集覆盖问题，这是一个经典的NP-完全问题。我们从两种不同的角度来研究和探讨，是否存在严格小于2的近似比的近似算法。首先，我们提出和研究了弱边问题。所谓弱边就是存在一个最优覆盖，只包含这条边的一个端点。我们证明了弱边问题也是一个NP-难问题，进一步我们分析了弱边问题的近似比与点集覆盖问题的近似比之间的关系，即有r=2-1/(a+1), 这里a是弱边问题的近似比, 而r是点集覆盖问题的近似比。这样我们就提供了一种新的研究点集覆盖问题的角度和方法: 通过研究弱边问题，如果能得到弱边问题的常数近似比, 则点集覆盖问题就有近似比严格小于2的近似算法。其次，我们给出了解点集覆盖问题的一种扩充的线性规划松弛算法(ELP)，该算法主要应用了如下的积极边简约法：若图中有三角形，去掉此三点，并将它们放入点覆盖；如图中无三角形，考虑积极边(ij），连结所有的 i点的邻点和j点的邻点，再去掉这两点及其相应的关联边。ELP 算法保证了只取 (i,j) 两点中的一点放入点覆盖。我们证明了ELP 算法对一类满足积极边假设的图，给出的点集覆盖的解的近似比为1.5。最后，我们发现：点集覆盖问题存在一种线性规划的表示形式，即所有奇数圈约束，再加上适当的积极边约束，就可以给出点覆盖问题的最优解。从而我们可以通过研究“适当的积极边约束”，来研究点覆盖问题。一种可能有效的方法就是利用线性规划松弛, 确定积极边：每次选择一条边, 它是所有可能的边中的这样的一条边，它使得相应的线性规划目标函数值增加量最小。然后我们研究这样给出的积极边约束与“适当的积极边约束”之间的近似比。目前, 我们正在研究用两种可能方法来估计和计算这种近似比。一种就是利用我们关于弱边的理论结果; 一种就是利用次模理论。我们将会继续这方面的研究工作。同时本项目也研究了一些相关的控制和优化问题，如张量优化问题，双二次优化问题等。依赖本项目的全部或部分资助，项目组主要成员共发表相关的学术论文18篇，参加国际国内学术会议十余人次；项目组成员出境访问交流4人次，接待境外专家来访五人次。组织国内小型优化学术交流会议1次。