4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This algorithm guarantees that the difference is at most $M$, which is the largest integer overall. But, it does not guarantee that the difference is at most the largest integer in the set with the larger sum (which may be smaller than $M$). Perhaps it was not clear in the original question; I clarified it. $\endgroup$ – Erel Segal-Halevi Nov 8 at 13:22
  • $\begingroup$ Yeah, this condition was not mentioned at all in the original question :P. The edited version seems harder: for example the case with array [2, 1, 1, 1, 1], a=1, b=4, does have a solution in the original formulation but not in the new. $\endgroup$ – Laakeri Nov 8 at 14:00
  • $\begingroup$ What if we run your algorithm $n$ times, each time with a different item designated as the largest item in set B. So in the first step, we look for a "balanced" partition in which the largest item is in B. If no such partition is found, then we look for a balanced partition in which the largest item is in A and the second-largest in B. etc. Does this work? $\endgroup$ – Erel Segal-Halevi Nov 11 at 13:09
  • $\begingroup$ I added an answer based on your algorithm. $\endgroup$ – Erel Segal-Halevi Nov 16 at 18:57
0
$\begingroup$

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.

$\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.