文件名称：论文研究-带核集分划问题的一个改进近似算法.pdf
文件大小：191KB
文件格式：PDF
更新时间：2022-10-10 05:07:29
论文研究
论文研究-带核集分划问题的一个改进近似算法.pdf, 设有整数集S={ $r_1,r_2; p_1, p_2,\cdots, p_n$ }, 这里$r_i\geq 0, 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.