The modified differencing method for the set partitioning problem with cardinality constraints

摘要: Abstract The set partitioning problem requires a of n numbers into K subsets so that the difference between maximum and minimum subset sums is minimized. This paper investigates with additional constraint cardinalities should be as balanced possible. It modifies differencing method Karmarkar Karp to ensure cardinality each either ⌈ ⌉ or ⌊ ⌋. modified algorithm preserves asymptotic quality method, is, does not exceed n−c log n, almost surely.