Indexed by：
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辑
ISSN： 1006-9232
Year： 2005
Issue： 7
Volume： 35
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： -1
Chinese Cited Count：
30 Days PV： 12
Affiliated Colleges：
