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

• 作者: 徐大川 杜东雷 韩继业
• 来源期刊: 中国科学A辑
• 学科: 数学
• 关键词: 稠密平分子图问题 表压缩问题 半定规划 近似比
• 年，卷（期）: 2005,（7）
• 页码范围: 745-756
• 页数: 12页
• 分类号: O1
• 字数: 5778字
• 语种: 中文
• DOI: 10.3321/j.issn:1006-9232.2005.07.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	韩继业	中国科学院数学与系统科学研究院应用数学研究所	15	195	8.0	13.0
2	徐大川	北京工业大学应用数理学院	18	30	3.0	4.0