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

？设有整数集s={$r_1,r_2;p_1,p_2,\cdots,p_n$},这里$r_i\geq0,p_j>0$(i=1,2;j=1,2,…,n),寻找一个s的分划p=($s_1,s_2$)使得:1)$r_i$属于不同子集,2)$s_1$与$s_2$中元素总和较大者尽可能地小.这是一个np-完备问题.其已有的线性时间算法近似比为8/7,文章在此基础上给了一个线性时间改进算法,它的近似比为10/9.