patternMinor
Equal partition up to one integer
Viewed 0 times
equalonepartitioninteger
Problem
In the partition problem, the task is to partition $n$ given integers into two subsets $A$ and $B$ with equal sum. This problem is known to be NP-hard, but it becomes easy if the "equal sum" requirement is replaced with the following:
The difference $|\sum_A - \sum_B|$ should be at most the largest integer in the set with the larger sum.
A solution always exists, and can be found using the following algorithm:
The sum in subset A is always at least as large as the sum in subset B, but if we remove the largest integer from subset A, then the sum in subset B is at least as large as the remainder. Hence, the partition is equal up to one integer.
MY QUESTION IS: what happens when there are cardinality constraints on the subsets? Formally, the task is to partition $n$ given integers into two subsets $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. The algorithm above does not work, and indeed an equal partition up-to-one-integer may not exist. What is an algorithm to decide whether such a partition exists?
The difference $|\sum_A - \sum_B|$ should be at most the largest integer in the set with the larger sum.
A solution always exists, and can be found using the following algorithm:
- Order the integers by descending value.
- Put the largest integer in subset A, the second in subset B, the third in subset A, etc.
The sum in subset A is always at least as large as the sum in subset B, but if we remove the largest integer from subset A, then the sum in subset B is at least as large as the remainder. Hence, the partition is equal up to one integer.
MY QUESTION IS: what happens when there are cardinality constraints on the subsets? Formally, the task is to partition $n$ given integers into two subsets $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. The algorithm above does not work, and indeed an equal partition up-to-one-integer may not exist. What is an algorithm to decide whether such a partition exists?
Solution
There is an $O(n \log n)$ algorithm for this problem.
To formalize, lets say that the task is to partition $n$ given integers into two partitions $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. Denote the maximum integer with $M$ and the sums of integers in $A$ and $B$ with $\sum_A$ and $\sum_B$. The partitions should satisfy that $|\sum_A - \sum_B| \le M$.
Start by putting the $a$ largest integers into $A$ and the $b$ smallest to $B$. Now, if $\sum_A < \sum_B - M$, there is no solution because we cannot make the sum of $A$ any larger. If $\sum_B - M \le \sum_A \le \sum_B + M$, the partition $(A, B)$ is a solution and we are ready. The case that is left is $\sum_B + M < \sum_A$. In this case, we can repeatedly choose the largest element of $A$ and the smallest element of $B$ and swap them. The difference $\sum_A - \sum_B$ changes by at most $2M$, so either we find a solution or maintain the invariant $\sum_B + M < \sum_A$. At some point we must find a solution, because $a$ is smaller than $b$, and thus $\sum_A$ will become smaller than $\sum_B$ by repeating this operation.
This can be implemented in $O(n \log n)$ with sorting and two pointers.
To formalize, lets say that the task is to partition $n$ given integers into two partitions $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. Denote the maximum integer with $M$ and the sums of integers in $A$ and $B$ with $\sum_A$ and $\sum_B$. The partitions should satisfy that $|\sum_A - \sum_B| \le M$.
Start by putting the $a$ largest integers into $A$ and the $b$ smallest to $B$. Now, if $\sum_A < \sum_B - M$, there is no solution because we cannot make the sum of $A$ any larger. If $\sum_B - M \le \sum_A \le \sum_B + M$, the partition $(A, B)$ is a solution and we are ready. The case that is left is $\sum_B + M < \sum_A$. In this case, we can repeatedly choose the largest element of $A$ and the smallest element of $B$ and swap them. The difference $\sum_A - \sum_B$ changes by at most $2M$, so either we find a solution or maintain the invariant $\sum_B + M < \sum_A$. At some point we must find a solution, because $a$ is smaller than $b$, and thus $\sum_A$ will become smaller than $\sum_B$ by repeating this operation.
This can be implemented in $O(n \log n)$ with sorting and two pointers.
Context
StackExchange Computer Science Q#116839, answer score: 3
Revisions (0)
No revisions yet.