稠密平分子图与表压缩问题的近似算法  

作　　者：徐大川[1] 韩继业[2] 杜东雷 

机构地区：[1]北京工业大学应用数理学院,北京100022 [2]中国科学院数学与系统科学研究院应用数学研究所,北京100080 [3]Faculty of Administration University of New Brunswick,P.O.Box 4400,Fredericton,NB E3B 5A3,Canada

出　　处：《中国科学（A辑）》2005年第7期745-756,共12页Science in China(Series A)

基　　金：国家自然科学基金(批准号:10401038;10171108;10271002;70271014)北京工业大学博士科研启动基金NSERC基金(10004901)资助项目

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

关 键 词：近似算法 分子图 压缩 稠密 三角不等式 半定规划 NP问题 贪婪算法 解决问题 SDP 近似比 TCP 松弛 

分 类 号：O157.5[理学—数学]