Abstract：
给出两个NP问题(稠密平分子图和表压缩)的改进的近似算法.基于半定规划(SDP)松弛和巧妙的舍入技巧,首先给出稠密平分子图问题(DSP)的0.5982-近似算法,表压缩问题(TCP)的0.5970-近似算法.然后,通过增加三角不等式得到更紧的SDP松弛,把前面的比值分别改进到0.6243和0.6708.针对TCP得到的结果改进了简单贪婪算法的0.5近似比,因此回答了Anderson提出的未解决问题.
Keyword：
Reprint Author's Address：
Email：
Source ：
中国科学(A辑:数学)
Year： 2005
Issue： 07
Page： 745-756
Cited Count：
WoS CC Cited Count： 0
SCOPUS Cited Count：
ESI Highly Cited Papers on the List： 0 Unfold All
WanFang Cited Count：
Chinese Cited Count：
30 Days PV： 3
Affiliated Colleges：
