1

Given a set $A$ of numbers and the number of desired subsets, $n$, how can I divide the numbers in set $A$ into $n$ subsets where each number in $A$ is used in one and only one subset and the sum of the numbers in each subset is optimally balanced?

If the subsets are named $S_1$ through $S_n$ then I would define the solution as the arrangement of the members of set $A$ that yielded the smallest value for

$$\max\left\{\sum S_1,\sum S_2,\ldots,\sum S_n\right\}-\min\left\{\sum S_1,\sum S_2,\ldots,\sum S_n\right\}\;.$$

As a practical matter, given that the size of set $A$ is small, a brute force solution is fine. I just need it to be accurate and reasonably straight forward to program.

Peter Taylor
  • 13,425
Ted Cohen
  • 119
  • I fail to understand the three close votes. This is a perfectly legitimate question, albeit probably a rather hard one. – Brian M. Scott Jan 14 '15 at 17:56
  • You say $A$ is small, but how small? This is an $NP$-complete problem (see e.g. the related Subset Sum problem), so $|A|=40$ is already large. – TonyK Jan 15 '15 at 12:04
  • We have heard of the traveling salesman problem. To me this is the "whining children problem". You cut the cake at the birthday party and you always hear "his piece is bigger than mine". We need to optimally divide orders between employees and we always hear "He got more" or "He got bigger" or "He got better". n is easy to define, that is the number of employees. Today that number is 21. I can control A by how often during the day I partition the orders. I estimate that A would be 20 if I partition every hour or 160 if I partition once per day. – Ted Cohen Jan 15 '15 at 13:11
  • That should have been |A|=20 and |A|=160. It won't let me fix the comment. – Ted Cohen Jan 15 '15 at 13:19
  • I am working on a brute force approach right now where I find all of the combinations of A. For each combination that I find, call it B, I set it aside and recursively apply the algorithm to the set that remains after I remove the elements in B from A. I am not very far along on it, but I am sure that I can do it. I just did not want to reinvent the wheel if there is an established solution. Years ago, I wrote a program that solved the "Six degrees of Kevin Bacon" for any two actors using the IMDB database. Despite the size of the sets involved, the solutions where near instantaneous. – Ted Cohen Jan 15 '15 at 13:24
  • Tony, Thank you for providing the reference to NP-Complete. Reading about it implies that there is not (at this time) a known algorithm that will provide the optimal solution and that current approaches use approximations to get close. I know the sum of A and I know n so I know that an ideal solution would result in n subsets that each sum to Sum(A)/n. If I abandon possible solutions where the sum of any subset deviates from the ideal sum, by a certain amount, maybe I can arrive at a brute force answer using the computational power that I have available. – Ted Cohen Jan 15 '15 at 13:40
  • The computational power of disgruntled employees is rumoured to be superpolynomial. Perhaps you can get them to solve the problem themselves by some kind of bidding process. (BTW: please include the magic word "@TonyK" in any response. That way I get notified.) – TonyK Jan 20 '15 at 23:38
  • Thank you again @TonyK, I had no idea that notifications worked that way. In theory they could bid on business by offering to take better business at a lower commission rate. I think the owners would rather have them working on deliverables for clients rather than researching new business, but experienced employees would not have to research much as their experience would tell them what to bid. Business is currently distributed by a person. The simple algorithm that I wrote (give it to the person that has the least) is already out performing the human. If not perfect, it is better. – Ted Cohen Jan 21 '15 at 00:33

0 Answers0