I apologize if I did not use the terminology entirely correctly in the title. This problem seems to me quite similar to an assignment problem and likely something that occurs in real life in business.

The problem:

  • In this problem, we have a set of assets (in the economics/finance sense) $\left\{ a_i \right\} $ with values $\left\{v_i\right\}$ (always positive) respectively, and a set of people $\left\{p_j\right\}$. For each person, we have a (positive) value $\left\{g_j\right\}$ (respectively), which is our goal for the total value we want to assign to this person.
  • We can assign multiple assets to a single person but cannot assign an asset to more than one individual or divide an asset in any way. Given such an assignment $f: a_i \mapsto p_j$, we can calculate the total value assigned to person $p_j$, call it $T_j(f)$, as the sum of the values of all assets assigned to person $p_j$. We wish to find an assignment $f$ which minimizes $\max_j(|T_j(f) - g_j|)$, i.e., we don't want to have a large error for even a single individual.

I'll describe my questions and then my current attempts/idea.


  1. Does this problem have a name, either with the current objective function I mentioned or maybe minimizing something else, e.g., the sum of absolute errors or squares of errors?
  2. The main question is finding an efficient way to solve this. I am looking to solve it with 10 people and 60 assets, i.e., considering $10^{60}$ possible assignments. So a brute-force method will not work.

My ideas:

  1. my only idea, except for going through all options, is to set some maximum value for that error I mentioned, $\max_j(|T_j(f) - g_j|)$, and this allows to prune the search tree (the search-tree I am thinking of is one where the first level is the assignment of asset $a_1$ to each of the persons, the second level is the assignment of $a_2$, etc.) whenever the total value for even a single individual goes above that. This should do a lot of pruning, and I know from experience with my datasets that, in most cases, it is possible to find a solution with a relatively small error (an error of the type I described).

But this pruning method seems not to be that fast/efficient.


1 Answer 1


The problem you describe is strongly NP-hard since it generalizes the 3-PARTITION problem. Hence you can expect no efficient algorithm for it, unless P = NP.

To see that it generalizes the 3-PARTITION problem, take an instance S of 3-PARTITION that is composed of 3m positive integers summing to mT. Now consider the following instance of your problem: there are m persons, each with a goal of T. There are also 3m assets, one for each positive integer in S, with the corresponding value. Then you can find an assignment with cost zero (that is, meet exactly the goal of each person) if and only if the 3-PARTITION instance has a solution.

  • $\begingroup$ Are you sure the "if and only if" holds here? my problem does not have the constraint that exactly three assets need to be assigned to each person, which seems to exist in the 3-partition problem. OTOH intuitively I'd expect the problem to be even harder without that constraint, but not sure if it is necessarily the case. $\endgroup$
    – edwi
    Jan 9 at 23:31
  • $\begingroup$ Yes, because (as mentioned on the Wikipedia page) 3-partition is NP-hard even when each integer is strictly between T/4 and T/2. Your problem does not have the contraint you mention, but nevertheless the only way to make the error zero is to meet each person's goal exactly, which in turn implies each person gets exactly 3 assets summing to T: if they got 2 (or less), the sum would be too low (<T), and if they got 4 (or more), the sum would be too high (>T). $\endgroup$
    – Vincenzo
    Jan 10 at 11:54
  • $\begingroup$ Could you please accept the answer, or explain what is wrong with it? $\endgroup$
    – Vincenzo
    Jan 13 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.