Approximation of dense-n/2-subgraph and table compression problems

摘要：

针对两个NP难问题:dense-n/2-subgraph(DSP)和table compression(TCP),我们给出改进的近似算法.基于SDP松弛和巧妙和舍入技巧,对于DSP和TCP我们分别给出0.5982和0.5970近似算法.通过增加三角不等式,我们分别得到改进的近似比:0.6243和0.6708.关于TCP的结果改进了贪婪算法导出的0.5近似比,从而解决了Anderson提出的open问题.

关键词： NP难问题 数字信号处理 通信协议 近似算法 电信数学

作者: XU Dachuan HAN Jiye DU Donglei

作者单位: College of Applied Sciences,Beijing University of Technology(China Beijing) Institute of Applied Mathematics,Academy of Mathematics and Systems Sciences,Chinese Academy of Scie Faculty of Administration,University of New Brunswick(Canada Fredericton)

会议类型: 国内会议

会议名称: 中国运筹学会第七届学术交流会

会议地点: 青岛

会议语种:英文

页码: 1342-1348

在线出版日期: 2004-10-01（万方平台首次上网日期，不代表论文的发表时间）