首页 | 本学科首页   官方微博 | 高级检索  
     

关于最小测试集的线性规划松弛近似
引用本文:崔鹏 刘红静. 关于最小测试集的线性规划松弛近似[J]. 计算机科学, 2005, 32(10): 157-159
作者姓名:崔鹏 刘红静
作者单位:[1]中国人民大学信息资源管理学院,北京100871 [2]保定市财贸学校,保定071000
摘    要:目前最小测试集的最佳近似比是贪心算法的2 ln n+o(1).这个近似比能否改进是一个公开的问题.本文讨论了最小测试集的基于线性规划松弛的近似比证明方法的能力问题.我们证明最小测试集的整性间隙至少为0.72 ln n,而且最小测试集整性间隙的系数可以与最小集合覆盖的整性间隙的系数一样大.另外,我们说明加权最小测试集的贪心算法的近似比不能通过对偶拟合方法改进超过一个常数.

关 键 词:最小测试集  贪心算法  整性间隙  对偶拟合

On LP-relaxation Approximation of Minimum Test Set
CUI Peng,LIU Hong-Jing. On LP-relaxation Approximation of Minimum Test Set[J]. Computer Science, 2005, 32(10): 157-159
Authors:CUI Peng  LIU Hong-Jing
Affiliation:1 Computer Science and Technology Departmant, Peking Univercity, Beijing 100871;2 School of Finance and Trade of Baoding, Baoding 071000
Abstract:The up-to-date best approximation ratio of minimum test set is 21nn+o(1)of the greedy algorithm. It is an open problem if this approximation ratio can be improved. This paper discusses the ability of the methods for proof of the approximation ratios based on the LP-relaxation. We prove the integrality gap of minimum test set is at least 0.72 In n and the coefficient of the integrality gap of minimum test set can be as large as that of minimum set cover. Moreo- ver, we show one cannot improve the approximation ratio of the greedy algorithm for weighted minimum test set by more than a constant.
Keywords:Minimum test set   Greedy algorithm   Integrality gap   Dual fitting
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《计算机科学》浏览原始摘要信息
点击此处可从《计算机科学》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号