Multi-way KK differencing algorithm vs. Greedy algorithm?

Question

It's proven that, the Karmarkar-Karp's differencing algorithm always performs better than greedy for 2-way partitioning problems, i.e. partitioning set of n integers to 2 subsets with equal sums. Can this be extended to k-way partitioning as well? If not, is there any example where greedy performs better than KK in k-way partitioning?

Answer 1

KK's superiority cannot be generalized for the k-way partitioning. In fact, it's easier to give a counter-example where the Greedy algorithm is performing better. Let the performance measure be the maximum subset sum of the final partition. Now, take this set of integers:

S = [10 7 5 5 6 4 10 11 12 9 10 4 3 4 5] and k=4 (partitioning into 4 equal subsets)

Fast forward, KK algorithm gives the result of [28, 26, 26, 26] whereas the greedy gives the final partition of [27, 27, 27, 24]. Since 28 > 27, greedy performed better for this example.

Answer 2

There is an issue with KK Algorithm solution provided.

• Sum(S) = 105
• Sum([28, 26, 26, 26]) = 106
• Sum([27, 27, 27, 24]) = 105

Greedy algorithm gives a result of

{{12, 6, 5, 4}{11, 7, 5, 4}{10, 10, 4, 3}{10, 9, 5}}
[27, 27, 27, 24]

KK algorithm gives a result of

{{5, 12, 6, 4}{5, 10, 7, 4}{5, 11, 10}{4, 3, 10, 9}}
[27, 26, 26, 26]

Since the highest sums are equal (27=27) and KK's lowest sum is greater than the Greedy Algorithm's (26>24), KK algorithm performs better. There are circumstances where Greedy Algorithm can still perform better than KK, but this example isn't one of them.