%0 Journal Article
%T On LP-relaxation Approximation of Minimum Test Set<br>关于最小测试集的线性规划松弛近似
%A CUI Peng
%A LIU Hong-Jing
%A <br>崔鹏
%A 刘红静
%J 计算机科学
%D 2005
%I 
%X 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.
%K Minimum test set
%K Greedy algorithm
%K Integrality gap
%K Dual fitting<br>最小测试集
%K 贪心算法
%K 整性间隙
%K 对偶拟合
%K 线性规划松弛
%K 测试集
%K 近似比
%K 最小
%K 贪心算法
%K 证明方法
%K 集合覆盖
%K 拟合方法
%K 间隙
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=4966E8A1EE562AF3&yid=2DD7160C83D0ACED&vid=9971A5E270697F23&iid=F3090AE9B60B7ED1&sid=0B4F496D54044D86&eid=BA79719BCA7341D5&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=10