| 稠密平分子图与表压缩问题的近似算法 |
| |
| 引用本文： | 徐大川,韩继业,杜东雷.稠密平分子图与表压缩问题的近似算法[J].中国科学A辑,2005,35(7):745-756. |
| |
| 作者姓名： | 徐大川 韩继业 杜东雷 |
| |
| 作者单位： | (1)北京工业大学应用数理学院 ,北京 100022 ,中国;(2)中国科学院数学与系统科学研究院应用数学研究所 ,北京 100080 ,中国;(3)Faculty of Administration, University of New Brunswick, P. O. Box 4400, Fredericton, NB E3B 5A3, Canada |
| |
| 基金项目： | 国家自然科学基金(批准号:10401038,10171108,10271002,70271014)
北京工业大学博士科研启动基金
NSERC基金(10004901)资助项目 |
| |
| 摘 要： | 给出两个NP问题(稠密平分子图和表压缩)的改进的近似算法. 基于半定规划(SDP)松弛和巧妙的舍入技巧, 首先给出稠密平分子图问题(DSP)的0.5982-近似算法, 表压缩问题(TCP)的0.5970-近似算法. 然后, 通过增加三角不等式得到更紧的SDP松弛, 把前面的比值分别改进到0.6243和0.6708. 针对TCP得到的结果改进了简单贪婪算法的0.5近似比, 因此回答了Anderson提出的未解决问题.
|
| 关 键 词： | 表压缩问题 半定规划 近似比 稠密平分子图问题 |
| 收稿时间： | 2005-03-31 |
| 修稿时间： | 2005年3月31日 |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《中国科学A辑》浏览原始摘要信息 |
| 点击此处可从《中国科学A辑》下载免费的PDF全文 |
|
