-1

I have n numbers and I want to distribute them among k containers (n/k numbers in each container) such that the difference between each two container is minimized.
1. Is 'balanced partitioning' the best map of this question?
2. I found all of the 'balanced partition' discussions on 2 containers (such as here or here). How can I extend the solutions for more containers?

Shannon
  • 985
  • 3
  • 11
  • 25
  • So what have **YOU** tried / researched so far? Share your findings. – MrSmith42 Dec 11 '18 at 12:19
  • Possible duplicate of [Packing a small number of packages into a fixed number of bins](https://stackoverflow.com/questions/53084341/packing-a-small-number-of-packages-into-a-fixed-number-of-bins) – juvian Dec 11 '18 at 14:36
  • @MrSmith42, If I have k as power of 2, I can use divide and conquer and partition problem (so in each phase, I would partition n numbers two 2 groups) – Shannon Dec 13 '18 at 23:41
  • @juvian, thanks for the link. In that link, there is an objective function of minimizing the left-out terms. I don't have any objective function, how can I map it to linear programming? – Shannon Dec 13 '18 at 23:42
  • @Shabnam your objective is that the difference between two containers is minimized. Your restriction is that n/k numbers go in each container – juvian Dec 14 '18 at 14:28

1 Answers1

1

Your problem is indeed a generalization of the well-known Partition problem. (see for example https://en.wikipedia.org/wiki/Partition_problem for more information on the subject), and hence it is a NP-hard problem.

Your problem is, to be more precise, the Multi-Way Number Partitioning, introduced in many articles recently, for example in https://www.ijcai.org/Proceedings/09/Papers/096.pdf and in http://www.mysmu.edu/faculty/kyriakos/IJCAI11.pdf.

Damien Prot
  • 573
  • 3
  • 7