带核集分划问题的一个改进近似算法

摘要：

设有整数集S=(r1,r2; p1, p2, …, pn}, 这里ri0, pj>0(I=1, 2; j=1, 2, …, n), 寻找一个S的分划P=(S*1, S*2)使得: 1) ri属于不同子集, 2) S*1与S*2中元素总和较大者尽可能地小. 这是一个NP-完备问题. 其已有的线性时间算法近似比为8/7, 文章在此基础上给了一个线性时间改进算法, 它的近似比为10/9.

关键词：带核集分划、近似算法、最坏情况分析

所属期刊栏目：23

分类号：O223(运筹学)

资助基金：国家自然科学基金10271110;高等学校优秀青年教师教学科研奖励计划

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

页数：共6页

页码：110-115