The constrained partition problem with kernels

The constrained partition problem with kernels is considered,which is to find a partition of the set Sinto 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 polyno-mial-time approximation scheme (FPTAS) with running times O(n) are designed.