【摘 要】
：
目前最小测试集的最佳近似比是贪心算法的2ln n+o(1).这个近似比能否改进是一个公开的问题.本文讨论了最小测试集的基于线性规划松弛的近似比证明方法的能力问题.我们证明最
论文部分内容阅读
目前最小测试集的最佳近似比是贪心算法的2ln n+o(1).这个近似比能否改进是一个公开的问题.本文讨论了最小测试集的基于线性规划松弛的近似比证明方法的能力问题.我们证明最小测试集的整性间隙至少为0.721nn,而且最小测试集整性间隙的系数可以与最小集合覆盖的整性间隙的系数一样大.另外,我们说明加权最小测试集的贪心算法的近似比不能通过对偶拟合方法改进超过一个常数.
其他文献
一直以来,中山市十分重视专业镇的建设,也取得了相当大的成绩,本文通过对中山市专业镇建设中面临的一些问题进行了分析,对政府在新的时代背景下应起的作用进行了论述,并且对
皮肤组织工程支架材料为种子细胞提供生长和代谢的环境,是人工皮肤研究中的重要内容,可按来源分为合成支架材料和天然支架材料.近几年的研究重点是:前者通过表面仿生技术增强
论述计算机光学元件制作的方法,着重介绍了灰度掩模技术,反应离子束刻蚀法和激光直写技术,并且说明了其在空间聚焦器上和激光雷达上的新应用.
试验了用2-甲基吲哚测定克仑特罗片的新方法.克仑特罗在酸性溶液中被亚硝酸钠重氮化后,能与2-甲基吲哚偶合成黄色化合物,该化合物的最大吸收波长λmax 389nm,摩尔吸光系数ε
利用Lebesgue-Stieljes积分,结合示性函数的有关性质证明了著名的Jordan公式和测度上下极限不等式.
产权制度是企业制度体系中的核心内容,选择适于自身发展的产权制度是国有企业生存、发展和繁荣的基础。本文从我国国企改革的必要性、改革以来的历程出发,分析了我国国企产权
研究Vlasov-Poisson-Fokker-Planck(VPFP)方程组的拟中性极限问题.通过使用紧致性理论和相对熵方法证明了VPFP方程组到不可压Euler方程的收敛性,这个结果在不可压Euler方程光滑解存在的时间区间上都成立.
根据用户定义的主观重视程度,综合考虑属性的缺省值情况以及信息系统中各属性的属性值个数,确定模式的综合重要度,进而得出模式的最小支持度.另外,提出剪枝技术剪除无意义的
数字人体计划作为一个大型的科学研究工程,利用计算机技术实现人体结构及功能的虚拟,将对未来医学及相关学科的发展将起到巨大的影响[1,2].目前,数字化虚拟人体计划的研究正
叙述了阿达玛变换光谱成像仪的原理及仪器构成,对阿达玛编码模板引起的光谱混叠现象进行了分析研究.从理论上导出了光谱混叠公式,并提出了光谱修正方法,仿真实验结果表明该方