超平面覆盖问题的参数化改进算法

摘要：

超平面覆盖问题是计算几何领域中一类典型的NP难问题,在实际生活中有着广泛的应用.针对NP难问题的难解性,人们提出了一些传统的方法用来求解这些NP难问题.但由于这些方法具有各自的局限性,不能满足实际应用中的各种需求,人们从新的理论角度为固定参数可解的NP难问题设计参数算法.通过深入分析直线覆盖问题(超平面覆盖问题的一个特例)的结构特征,并利用深度有界搜索树的方法,提出了一个时间复杂度为O(k3(0.736k)k+n logk)的确定性参数算法,极大地改进了当前最好的结果O((k/2.2)2k+n logk).通过对上述算法在高维空间中的进一步扩展,提出了关于超平面覆盖问题时间复杂度为O(dkd+1 (dk)!/((d!)kk!)+nd+1)确定性参数算法,对当前的最好结果O(kd(k+1)+nd+1)有较大改进.

关键词：计算几何、超平面覆盖问题、直线覆盖问题、固定参数可解、深度有界搜索树

所属期刊栏目：49

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金项目61073036,70921001;教育部高等学校博士学科点专项科研基金项目20090162110056

在线出版日期：2012-07-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：804-811