Heuristic algorithms for balanced multi-way number partitioning

摘要: Balanced multi-way number partitioning (BMNP) seeks to split a collection of numbers into subsets with (roughly) the same cardinality and subset sum. The problem is NP-hard, there are several exact approximate algorithms for it. However, existing solve only simpler, balanced two-way variant, whereas most effective algorithm, BLDM, may produce widely varying sums. In this paper, we introduce LRM algorithm that lowers expected spread in sums one third BLDM uniformly distributed odd cardinalities. We also propose Meld, novel strategy skewed distributions. A combination Meld leads heuristic technique consistently achieves narrower than BLDM.