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

项目名称： 关于点集覆盖问题近似算法及其相关问题的研究

项目编号： No.10971187

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 数理科学和化学

项目作者： 韩乔明

作者单位： 浙江财经学院

项目金额： 24万元

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

中文关键词： 点覆盖问题；NP-完全问题；近似算法；线性规划松弛方法；去边法

英文摘要：

英文关键词： vertex cover problem；NP-complete problem；approximation algorithm；linear programming relaxation；edge reduction