An Improved Approximation Algorithm for Partitioning Problem with Kernels
带核集分划问题的一个改进近似算法

设有整数集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.