高级检索
检索提示：高级检索多个条件检索时是按照顺序运算的：如 A或B与C 即:(A或B)与C
[期刊论文]
稠密平分子图与表压缩问题的近似算法
作者：
摘要：
给出两个NP问题(稠密平分子图和表压缩)的改进的近似算法.基于半定规划(SDP)松弛和巧妙的舍入技巧,首先给出稠密平分子图问题(DSP)的0.5982-近似算法,表压缩问题(TCP)的0.5970-近似算法.然后,通过增加三角不等式得到更紧的SDP松弛,把前面的比值分别改进到0.6243和0.6708.针对TCP得到的结果改进了简单贪婪算法的0.5近似比,因此回答了Anderson提出的未解决问题.
关键词：
作者机构：
通讯作者信息：
电子邮件地址：
相关关键词：
相关文章：
2005，中国科学A辑
2016，运筹学学报
2005，应用数学学报
2004，第六届中国青年运筹与管理学者大会
来源 ：
中国科学(A辑:数学)
年份： 2005
期： 07
页码： 745-756
被引次数：
WoS核心集被引频次： 0
SCOPUS被引频次：
ESI高被引论文在榜： 0 展开所有
万方被引频次：
中文被引频次：
近30日浏览量： 4
归属院系：
理学部
全文获取
外部链接：
