Equal partition up to one integer

Question

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:

• 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?

Answer 1

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.

Answer 2

W.l.o.g. assume the integers are ordered such that $x_1 \geq \cdots \geq x_n$.

@Laakeri presented an algorithm for finding a partition $(A,B)$ that satisfies:

• $\sum_B + x_1 \geq \sum_A \geq \sum_B - x_1$

His algorithm can be used to finding a partition that satisfies the stronger condition:

• $\sum_B + \max_{A} \geq \sum_A \geq \sum_B - \max_{B}$

The idea is to run his algorithm once for each combination of $\max{A},\max{B}$. The number of such combinations is linear in $n$, so the run-time of the algorithm will be $O(n^2)$.

First, assume that $x_1\in A$, so that $\max_{A}=x_1$. Now, $\max_B = x_k$ for some $k\in\{2,\ldots, a+1\}$ (since $x_1,\ldots, x_{k-1}$ are all in $A$). For each such $k$, we start with a partition in which $\sum_A$ is maximized (subject to the constraints), and proceed towards a partition in which $\sum_B$ is maximized (subject to the constraints). The goal is to find a partition that satisfies:

• $\sum_B + x_1 \geq \sum_A \geq \sum_B - x_k$

If in the initial partition $\sum_A < \sum_B - x_k$, then no solution exists for this $k$. If $\sum_B + x_1 \geq \sum_A \geq \sum_B - x_k$, we are done. If $\sum_B + x_1 < \sum_A$, then we start switching integers between A and B such that $\sum_A$ decreases and $\sum_B$ increases. Since the location of $x_1,\ldots,x_k$ is fixed, the switches involve only integers weakly smaller than $x_k$. So at each step, the difference between the sums changes by at most $2 x_k$. Since the "allowed range" for the difference has a size of $x_1 + k_x \geq 2 x_k$, the switch either brings us into the allowed range, or keeps the invariant $\sum_B + x_1 < \sum_A$. If we arrive at the final partition and still have $\sum_B + x_1 < \sum_A$, then a solution does not exist for this $k$ and we can move to the next $k$.

The case that $x_1\in B$ is handled analogously.