1
$\begingroup$

I've seen a number of questions and answers related to the partitioning problem of dividing a set into 2 subsets of equal size and sum that use greedy or dynamic programming solutions to get approximate answers. However, I am looking to split a set into 2 subsets of minimum difference in size but with a target ratio of sums.

I have tried variations of greedy algorithms that will work to minimize the largest difference of the two metrics at any point in the calculation, but this just results in a result that splits the difference between the two. I'm happy with an approximate solution since it needs to run in a reasonable amount of time.

$\endgroup$
2
$\begingroup$

The problem is NP-hard (assuming the numbers are represented in binary). If you could solve your problem efficiently, you could solve the Partition problem: Partition is the special case where the minimum difference is zero (and the target ratio is 1:1). Therefore, you should not expect any simple algorithm to be both efficient and always correct.

If you want a heuristic that gives an approximation, greedy algorithms are reasonable. I suggest you try adapting the standard algorithms for the Partition problem. Another approach is to use an integer linear programming solver.

$\endgroup$
0
$\begingroup$

As D.W.'s answer mentions, this is NP-hard to solve exactly as a known NP-hard problem is a special case of it.

To adapt any algorithm (exact or heuristic) for solving the Partition Problem to your problem, just add a single new "dummy" number calculated to make the ratio what you want. Suppose you want one of the sides to have sum $r$ times the other side's sum, and the total of all numbers is $t$. Since PP finds equal-sum partitions, we want to find a number $d$ to add such that $x+d=rx$, so that removing $d$ leaves us with a sum $x$ on one side, and $rx$ on the other side. Additionally we have that $x+d=rx=(t+d)/2$. We want to eliminate the unknown $x$ and rearrange to obtain $d$ in terms of the other, known, parameters:

$$ x+d=rx\\ x-rx=-d\\ x(1-r)=-d\\ x=d/(r-1) $$

Substituting this into $rx=(t+d)/2$ gives

$$ rd/(r-1)=(t+d/(r-1))/2\\ 2rd=t(r-1)+d\\ d(2r-1)=t(r-1)\\ d=t(r-1)/(2r-1) $$

The PP algorithm will assign this number to one of the two sides; afterwards, just discard it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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