限制性的带核元划分问题  

The constrained partition problem with kernels

作　　者：李伟东[1] 葛瑜[1] 张同全[2] 李建平[1] 

机构地区：[1]云南大学数学与统计学院数学系,云南昆明650091 [2]云南大学物理科学技术学院非线性中心,云南昆明650091

出　　处：《云南大学学报（自然科学版）》2010年第1期6-11,共6页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学研究基金资助项目(10561009;10861012);云南省中青年学术技术带头人基金资助项目(2007PY01-21);云南大学校基金资助项目(2007Q020C)

摘　　要：考虑了限制性的带核元划分问题,即将一个整数集合划分为2个子集,使得2个核元分别在不同的子集里且每个子集至多包含k个元素,这里n/2+1≤k≤n+1,目标使2个子集中元素之和的最小者达尽可能大.对一般的k,给出了全多项式时间近似方案(FPTAS).当k=n+1时,给出了线性时间内的多项式时间近似方案(PTAS)和全多项式时间近似方案(FPTAS).The constrained partition problem with kernels is considered, which is to find a partition of the set S into two disjoint subsets under the two constraints that two kernels belong to different subsets and eachsubset contains at most k elements, here n/2 ＋ 1 ~〈k ~〈 n ＋ 1. The objective is to maximize the minimum sum of elements in each of the two subsets. An full polynomial - time approximation scheme （FPTAS） is designed for the general k. For the special version where k = n ＋ 1, a polynomial -time approximation scheme （PTAS） and an full polynomial- time approximation scheme （FPTAS） with running times O（n） are designed.

关 键 词：带核元划分 近似算法 多项式时间近似方案 全多项式时间近似方案 

分 类 号：O223[理学—运筹学与控制论]