|
|
计算机科学 2005
关于最小测试集的线性规划松弛近似Keywords: 最小测试集贪心算法整性间隙对偶拟合线性规划松弛测试集近似比最小贪心算法证明方法集合覆盖拟合方法间隙 Abstract: 目前最小测试集的最佳近似比是贪心算法的2lnn＋o（1）.这个近似比能否改进是一个公开的问题.本文讨论了最小测试集的基于线性规划松弛的近似比证明方法的能力问题.我们证明最小测试集的整性间隙至少为0.72lnn,而且最小测试集整性间隙的系数可以与最小集合覆盖的整性间隙的系数一样大.另外,我们说明加权最小测试集的贪心算法的近似比不能通过对偶拟合方法改进超过一个常数.
|
