论文部分内容阅读
给出两个NP问题(稠密平分子图和表压缩)的改进的近似算法.基于半定规划(SDP)松弛和巧妙的舍入技巧,首先给出稠密平分子图问题(DSP)的0.5982-近似算法,表压缩问题(TCP)的0.5970-近似算法.然后,通过增加三角不等式得到更紧的SDP松弛,把前面的比值分别改进到0.6243和0.6708.针对TCP得到的结果改进了简单贪婪算法的0.5近似比,因此回答了Anderson提出的未解决问题.