1
$\begingroup$

Suppose we are asked to assign $N$ numbers into $K$ mutually exclusive groups. The partition has to satisfy two constraints for each group. The first one is that group $k$ must contain exactly $n_k$ elements. The second one is that the sum of all numbers in group $k$ must be in the range $(l_k, u_k)$. Of course we have $\sum_{k}^{K}n_k=N$.

For example, suppose there are 1000 numbers and the sum of the 1000 numbers is 1e5. We need to divide the 1000 numbers into 3 groups, say Group A, B and C. Group A, B and C must contain exactly 600 numbers, 300 numbers and 100 numbers, respectively. Additionaly, the sum of all numbers in Group A must be in the range (1e4, 7e4), the sum of Group B in the range (2e4, 4e4) and the sum of Group C in the range (1e4, 3e4).

Is there an algorithm to solve such a problem?

$\endgroup$

1 Answer 1

2
$\begingroup$

Of course there are algorithms, for example you can enumerate all possible partitions and check whether one of the partitions satisfies the constraints.

If the question is instead "Is there an efficient algorithm?" for such a problem, then unless P = NP the answer is no, since the problem includes 3-PARTITION as a special case (take $n_k=3$ for all $k$ and $l_1=u_1=...=l_K=u_K$).

$\endgroup$
2
  • $\begingroup$ Yes, I should have said that if there is an efficient algorithm. Brute force is certainly not viable given that $N$ could be very large. The 3-partition problem is indeed a special case, but its contraints are way more restrictive. So the question is, what is the best existing strategy to tackle the more general problem as posted? $\endgroup$
    – szx
    Apr 8, 2022 at 9:14
  • 1
    $\begingroup$ @szx, I suggest you ask a new question that clarifies what you are asking for. It will be important to define what you mean by 'best', as that can be subjective. If you mean that you are looking for a practical algorithm that is as fast as possible, then it will be important to tell us about the typical ranges of parameters (how large are the numbers, how large is N and K). I see you providing one example but I don't know what is the range of values for those parameters. $\endgroup$
    – D.W.
    Apr 8, 2022 at 17:24

Your Answer

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

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