Speeding Up 2-way Number Partitioning

摘要

Several algorithms exist for optimally solving 2-way number partitioning. When the cardinality of the multiset to partition is high enough, solving algorithms have to relay on search techniques with low memory complexity. Currently, CKK is the reference of such algorithms. Here we propose a contribution to speed-up CKK. We detail how to consider terminal nodes with 4, 5, 6 or more numbers left, when the original CKK considers a node terminal when it contains 4 or less numbers left. Using this idea, we propose new CKK implementations, which provide savings up to 70% of execution time with respect to the original CKK algorithm. We provide experimental evidence of the benefits of this approach on random number partitioning instances with numbers of 35 bits.