欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
考虑了限制性的带核元划分问题，即将一个整数集合划分为2个子集，使得2个核元分别在不同的子集里且每个子集至多包含k个元素，这里n／2＋1≤后≤n＋1，目标使2个子集中元素之和的最小者达尽可能大．对一般的k，给出了全多项式时问近似方案（FPTAS）．当k=／2＋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.
同期刊论文项目
同项目期刊论文
期刊信息
位置：