限制性的带核元划分问题

作者：李伟东 葛瑜 张同全 李建平带核元划分近似算法多项式时间近似方案全多项式时间近似方案

摘要：考虑了限制性的带核元划分问题，即将一个整数集合划分为2个子集，使得2个核元分别在不同的子集里且每个子集至多包含k个元素，这里n／2＋1≤后≤n＋1，目标使2个子集中元素之和的最小者达尽可能大．对一般的k，给出了全多项式时问近似方案（FPTAS）．当k=／2＋1时，给出了线性时间内的多项式时间近似方案（PTAS）和全多项式时间近似方案（FPTAS）．

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社