8
$\begingroup$

In the standard partition problem, we are given some numbers whose sum is $2s$ and have to decide whether they can be partitioned into two subset whose sum is $s$. It is known to be NP-hard.

However, assume that we are allowed to designate one of the numbers to be a "soft number" that can be cut it into an arbitrary number of pieces, where different pieces may be put into different subsets. Then the problem becomes easy: just arrange all numbers on a line in an arbitrary order, and cut the line into two sub-lines with the same sum.

QUESTION: Suppose we are given some numbers whose sum is $3s$, and have to decide whether they can be partitioned into three subsets whose sum is $s$, while using at most one soft number. What is the complexity of this problem?

  • If we are allowed to use two soft numbers, then the problem is again easy - we can solve it by arranging the numbers on a line as above.
  • If we are allowed to use zero soft numbers, then the problem is obviously hard - it is at least as hard as the problem of partitioning into two subsets.
  • If we are allowed to use one soft number, my guess is that the problem should still be hard, and we can somehow reduce to it from the standard partition problem, but I could not find the right reduction. So, is it easy or hard?

Another question: in case the problem is indeed NP-hard, can it be solved in pseudo-polynomial time like the two-subset partition problem?


CONCLUSION: Thanks a lot to all the repliers. To summarize the answers: the problem can be generalized to $n$ numbers whose sum is $k s$ that should be partitioned into $k$ subsets of sum $s$:

  • With no soft numbers, the problem is NP-hard - like the PARTITION problem.
  • With one or more soft number, for any fixed $k$, it can be decided in time $O(poly(n))$ whether an equal partition exists, and find one if it exists.
  • With $k-1$ or more soft numbers, an equal partition always exists and can be found in time $O(n)$.
$\endgroup$
  • 1
    $\begingroup$ A part of this problem is to find a subset whose sum is one third the sum of the whole set. However, I can't find the appropriate references saying this restricted subset-sum problem is NP-hard. $\endgroup$ – John Dvorak Jan 27 at 8:16
  • $\begingroup$ It's equivalent to that, actually, as the remainder is to bipartition the two thirds with one cut. $\endgroup$ – John Dvorak Jan 27 at 8:22
  • $\begingroup$ @JohnDvorak if we can solve the subset-sum problem then we can solve the problem in the question, but the opposite is not true: we may have a solution to the problem in question in which one number is cut into three fractions, and each subset contains one fraction. This solution does not solve the subset-sum problem. $\endgroup$ – Erel Segal-Halevi Jan 27 at 16:02
  • $\begingroup$ which is why I didn't post an answer. I'm convinced that the 1:2 partition problem is still np-complete (and more generally the partition problem for any fixed ratio), but I don't have any proof for it. But if it is indeed NP-hard, then so is the 3-way partition with one cut problem. $\endgroup$ – John Dvorak Jan 27 at 16:06
  • 1
    $\begingroup$ I have updated the problem formulation so that it is clear that a cuttable number can be cut into many pieces. (When I first read the problem, I thought that you are only allowed to cut one number once.) $\endgroup$ – Gamow Jan 27 at 16:37
3
$\begingroup$

Edit: The result is incorrect, see the discussion at the end.

Inspired by Mikhail Rudoy's answer, we can generalize to partitioning into $k$ parts with equal sum. The problem is polynomial time solvable for each constant $k$.

The input is $a_1,\ldots,a_n$ such that $a_n$ is the largest number. Mikhail's observations are, wlog,

  • the soft number is $a_n$
  • $a_i>\frac{a_n}{k-1}$ for each $i$

wlog, assume that the sum of $a_1,\ldots,a_{n-1}$ is $1$ (that is, $1=ks-a_n$). Note that $a_n \geq \frac{1}{n-1}$, so $a_i > \frac{1}{(k-1)(n-1)}>\frac{1}{kn}$ for each $i$. The problem is equivalent to partitioning the numbers $a_1,\ldots,a_{n-1}$ into $k$ subsets such that the sum of each subset is at most $s := \frac{1+a_n}{k}$.

We consider a restriction of the multiple knapsack problem. Define the $k$-knapsack problem as an instance of the multiple knapsack problem with $k$ knapsacks of the same capacity, where the value of each item equals the weight of the item.

Let the input for the $k$-knapsack problem be $a_1,\ldots,a_{n-1}$, and each knapsack has capacity $s$. The following claim is clear.

Claim: A $(1-\frac{1}{kn})$-approximation algorithm for the $k$-knapsack problem returns $1$, if and only if all the numbers $a_1,\ldots,a_{n-1}$ can be packed into the $k$ knapsacks.

By the above claim, we just have to find a $(1-\frac{1}{kn})$-approximation algorithm for the $k$-knapsack problem.

Claim: There is a pseudopolynomial time algorithm for knapsack generalizes for $k$-knapsack for each constant $k$.

Proof: Define $D[b_1,\ldots,b_k,i]$ to be the maximum value using elements $a_1,\ldots,a_i$, where the knapsack has capacity $b_1,\ldots,b_k$. The recurrence relation is $D[b_1,\ldots,b_k,i+1] = \max( \max_{j} (D[b_1,\ldots,b_j-a_{i+1},b_k,i])+a_{i+1},D[b_1,\ldots,b_k,i])$. The base case are simple. The running times is $O(s^kkn)$.

It is standard to obtain an FPTAS by scaling all numbers and round to integers, see section 5 of this. This means we can find a $(1-\frac{1}{kn})$-approximation to $k$-knapsack problem in polynomial time. Therefore for each constant $k$, the original problem can be decided in polynomial time.

The above is incorrect, due to the pseudopolynomial time algorithm does not transform into an FPTAS. However, the approach might still give us some insight because we have a very special case of $k$-knapsack problem.

$\endgroup$
  • $\begingroup$ I found this paper: epubs.siam.org/doi/abs/10.1137/S0097539700382820 which shows a PTAS for multple-knapsack. How do you obtain an FPTAS from it? (did you mean that there is an FPTAS for the special case in which the values are equal to the weights?) $\endgroup$ – Erel Segal-Halevi Feb 6 at 19:06
  • $\begingroup$ I have made an update. The FPTAS is for the case when $k$ is a constant. If the number of knapsacks is part of the input, there is no FPTAS. $\endgroup$ – Chao Xu Feb 6 at 20:04
  • $\begingroup$ Hi Chao, we are working on a paper in which this result is useful. Would you like to join? If so then please write me an email. $\endgroup$ – Erel Segal-Halevi Apr 18 at 4:36
5
+50
$\begingroup$

The largest number is the soft number

I claim that for any instance of your problem, if the instance is solvable (it is possible to partition the numbers using one soft number) then it is possible to solve the instance using the largest number as the sole soft number. This is easy to prove: any solution can be modified into a solution with the largest number as the soft number; simply place the number that is currently the soft number into the partition that contains the largest number and split the largest number among the parts of the partition instead.

Packing problem

Here is a problem that I will call the packing problem:

The input consists of a list of positive numbers $a_1, a_2, \ldots, a_k$ and one final number $\ell$ such that $\ell \ge a_i$ for all $i$. Define $s = \frac{1}{3}\left(\ell + \sum_{i = 1}^ka_i\right)$. Then the problem is to partition the list of $a_i$s into three parts such that each part has sum at most $s$.

I claim that the packing problem with inputs $a_1, \ldots, a_k$ and $\ell$ is equivalent to your problem with input list $a_1, \ldots, a_k, \ell$. If it's possible to pack the numbers $a_1, \ldots, a_k$ into three groups each of sum at most $s$ then you can use $\ell$ as a soft number to round out each of the sums to exactly $s$; thus you have a partition of $a_1, \ldots, a_k, \ell$ into three groups of sum $s$ using one soft number. If on the other hand $a_1, \ldots, a_k, \ell$ can be partitioned into three groups of sum $s$ using one soft number then the list can be partitioned into three groups of sum $s$ using $\ell$ as the soft number (by the result from the previous section). In this case the grouping of the $a_i$s into three parts satisfies the condition that each part has sum at most $s$.

The packing problem with no small numbers

Say that an instance of the packing problem "has no small numbers" if for every $i$, $a_i > \frac{\ell}{2}$. I claim that you can reduce the packing problem to the packing problem with no small numbers.

Suppose that in packing problem instance $(a_1, \ldots, a_k), \ell$ some $a_i$ has $a_i \le \frac{\ell}{2}$. WLOG suppose $a_k$ is this $a_i$. Then I claim the packing problem instance $(a_1, \ldots, a_{k-1}), \ell+a_k$ is equivalent to the original instance. Notice that the value $s$ remains the same in both instances.

Certainly if you can pack the numbers $a_1, \ldots, a_k$ into three groups with each group having sum at most $s$ then you can pack the numbers $a_1, \ldots, a_{k-1}$ into three groups with each group having sum at most $s$.

On the other hand, suppose you can pack the numbers $a_1, \ldots, a_{k-1}$ into three groups with each group having sum at most $s$. For each of the three groups, consider the value $s$ minus the sum of the elements in the group. Call these values $e_1, e_2, e_3$; here $e_i$ is the amount of "empty space" in group $i$. We know that $e_1 + e_2 + e_3$, the total empty space, is equal to $3s - \sum_{i = 1}^{k-1}a_i$ (total space $3s$ minus space used $\sum_{i = 1}^{k-1}a_i$). But $3s - \sum_{i = 1}^{k-1}a_i = a_k + \ell$ by the definition of $s$. Thus, the three groups have $a_k + \ell$ empty space in total. Then since $a_k < \frac{\ell}{2}$, we know that the total empty space is more than $3a_k$. By the pigeon hole principle, at least one of the groups has $a_k$ or more empty space in it. Thus, we can add element $a_k$ to one of the groups and end up with a packing of the numbers $a_1, \ldots, a_k$ into three groups with each group having sum at most $s$.

Thus, in order to solve your problem, it is sufficient to solve just the packing problem with no small numbers.

Lemma 1

Lemma statement:

Suppose we can partition $a_1, \ldots, a_k$ into groups 1 and 2 such that group 2 has an even number of elements and the sum of the elements in group 1 is in the interval $\left[s - \frac{\ell}{2}, s\right]$. Then it is possible to further partition group 2 into two subgroups 2a and 2b each of which has sum at most $s$. Notice that groups 1, 2a, and 2b are a solution of the packing problem instance.

Here's a proof.

Tentatively assign half of the elements of group 2 to subgroup 2a and the other half to subgroup 2b. Create a matching between the elements of the two subgroups. Swap these pairs between the two groups, one pair at a time. If there are $2n$ elements in group 2 then this process passes through exactly $n+1$ possible partitions of group 2 into subgroups 2a and 2b. I claim that at least one of those partitions has both subgroups with sum less than $s$.

Let $S_{2a}$ and $S_{2b}$ be the sums of the two subgroups (we allow these values to change as the groups change).

At each step of the above process, group 2a gains one element and loses another. Since each element has value between $\frac{\ell}{2}$ and $\ell$, we can conclude that at each step of the above process, $S_{2a}$ changes by at most $\frac{\ell}{2}$.

Also, the final value of $S_{2a}$ is equal to the initial value of $S_{2b}$ since by the end of the process the groups have entirely swapped.

Let $A$ be the average value of $S_{2a}$ and $S_{2b}$. Note that this is constant as the groups change. We know that the initial and final values of $S_{2a}$ average to $A$ (since the initial and final values of $S_{2a}$ equal the initial values of $S_{2a}$ and $S_{2b}$). Thus, $A$ must be between the initial and final values of $S_{2a}$. As we change the groups, the value of $S_{2a}$ takes steps of size at most $\frac{\ell}{2}$ from one side of $A$ to the other. From this, we can conclude that at some point, the value of $S_{2a}$ must be within half of the maximum step size ($\frac{\ell}{4}$) of $A$. Since $S_{2b}$ always has the same distance from $A$ as $S_{2a}$, we can conclude that at some point, both sums $S_{2a}$ and $S_{2b}$ are within $\frac{\ell}{4}$ of $A$.

$3s - \ell - (S_{2a} + S_{2b})$ is the sum of the elements of group 1; thus, $3s - \ell - (S_{2a} + S_{2b}) \ge s - \frac{\ell}{2}$ (by the condition on the sum of group 1). Rearranging, we have that $(S_{2a} + S_{2b}) \le 2s - \frac{\ell}{2}$. Therefore, the average of $S_{2a}$ and $S_{2b}$ is at most $s - \frac{\ell}{4}$. Then at the time that both $S_{2a}$ and $S_{2b}$ are within $\frac{\ell}{4}$ of $A$, we see that they are both at most $s$ as desired.

Case 1: $k = 3n$

Sum the $n$ smallest $a_i$s and also the $n$ largest $a_i$s.

If the $n$ smallest $a_i$s sum to more than $s$, then no group can have $n$ or more elements (as any choice of $n$ elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least $n$ elements. Thus, in this case there is no solution to the packing problem instance.

If the $n$ largest $a_i$s sum to at most $s$, then every choice of $n$ elements has a sum of at most $s$. In this case, simply partitioning the elements into three groups of equal size solves the packing problem instance.

The only remaining case is that the smallest $n$ elements sum to at most $s$ and the largest $n$ elements sum to more than $s$. As in the lemma, we can slowly transition between these two sets: start with a group initialized with the smallest $n$ elements and swap elements until the group has the largest $n$ elements. Each step moves the sum of the group by at most $\frac{\ell}{2}$ (by the same logic as in the proof of the lemma) and the sum crosses the value $s$ at some point in this process. Therefore, either immediately before or immediately after crossing the value $s$, the sum is less than $s$ but less by at most $\frac{\ell}{2}$. In other words, at some point in this process, the group has a sum in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

Case 2: $k = 3n+1$

Sum the $n+1$ smallest $a_i$s and also the $n+1$ largest $a_i$s.

If the $n+1$ smallest $a_i$s sum to more than $s$, then no group can have $n+1$ or more elements (as any choice of $n+1$ elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least $n+1$ elements. Thus, in this case there is no solution to the packing problem instance.

If the $n+1$ largest $a_i$s sum to at most $s$, then every choice of $n+1$ elements has a sum of at most $s$. In this case, simply partitioning the elements into three groups of size $n$, $n$, and $n+1$ solves the packing problem instance.

The only remaining case is that the smallest $n+1$ elements sum to at most $s$ and the largest $n+1$ elements sum to more than $s$. As in the previous case, we can slowly transition between these two sets: start with a group initialized with the smallest $n+1$ elements and swap elements until the group has the largest $n+1$ elements. Each step moves the sum of the group by at most $\frac{\ell}{2}$ (by the same logic as in the proof of the lemma) and the sum crosses the value $s$ at some point in this process. Therefore, either immediately before or immediately after crossing the value $s$, the sum is less than $s$ but less by at most $\frac{\ell}{2}$. In other words, at some point in this process, the group has a sum in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

Case 3: $k = 3n+2$ first easy subcase

Sum the $n$ smallest $a_i$s and the $n$ largest $a_i$s.

If either value is in the interval $[s-\frac{\ell}{2}, s]$, immediately apply the lemma with that choice of $n$ elements as group 1 and the remaining $2n+2$ elements as group 2. This allows us to find a solution to the packing problem instance.

If the $n$ smallest $a_i$s sum to less than $s-\frac{\ell}{2}$ and the $n$ largest $a_i$s sum to more than $s$ then we can start with the $n$ smallest $a_i$s and swap elements until we end up with the $n$ largest $a_i$s. At each step the sum moves at most $\frac{\ell}{2}$, so at some point in this process we have a group of $n$ elements whose sum is in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n+2$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

If the $n$ smallest $a_i$s sum to more than $s$, then no group can have $n$ or more elements (as any choice of $n$ elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least $n+1$ elements. Thus, in this case there is no solution to the packing problem instance.

The only remaining case is that both the $n$ smallest and $n$ largest $a_i$s add to less than $s-\frac{\ell}{2}$.

Case 3: $k = 3n+2$ second easy subcase

Sum the $n+2$ smallest $a_i$s and the $n+2$ largest $a_i$s.

If either value is in the interval $[s-\frac{\ell}{2}, s]$, immediately apply the lemma with that choice of $n+2$ elements as group 1 and the remaining $2n$ elements as group 2. This allows us to find a solution to the packing problem instance.

If the $n+2$ smallest $a_i$s sum to less than $s-\frac{\ell}{2}$ and the $n+2$ largest $a_i$s sum to more than $s$ then we can start with the $n+2$ smallest $a_i$s and swap elements until we end up with the $n+2$ largest $a_i$s. At each step the sum moves at most $\frac{\ell}{2}$, so at some point in this process we have a group of $n+2$ elements whose sum is in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

If the $n+2$ largest $a_i$s sum to at most $s$, then every choice of $n+2$ elements has a sum of at most $s$. In this case, simply partitioning the elements into three groups of size $n$, $n+1$, and $n+1$ solves the packing problem instance.

The only remaining case is that both the $n+2$ smallest and $n+2$ largest $a_i$s add to more than $s$.

Case 3: $k = 3n+2$ hard subcase

Suppose neither of the above two subcases handled the instance. Then we know the following:

  • both the $n$ smallest and $n$ largest $a_i$s add to less than $s-\frac{\ell}{2}$.
  • both the $n+2$ smallest and $n+2$ largest $a_i$s add to more than $s$.

Since the $n+2$ smallest $a_i$s add to more than $s$, no group can have $n+2$ or more elements. The only way this is possible to accomplish is if the groups have sizes $n$, $n+1$, and $n+1$.

Note that since the $n$ largest $a_i$s add to less than $s-\frac{\ell}{2}$, it doesn't matter what elements are in the group of size $n$: that group will have sum less than $s$ anyway. Clearly, we can modify any solution by swapping the $n$ largest $a_i$s into the group of size $n$. These swaps only decrease the sums of the other two groups, so there exists a solution to the packing problem instance if and only if there exists a solution in which the $n$ largest $a_i$s form one of the groups.

Thus, the task at hand is simply this: is it possible to partition the $2n+2$ smallest $a_i$s into two groups of size $n+1$ such that each of those two groups has sum at most $s$. WLOG suppose that the $a_i$s are in increasing order so that the $2n+2$ smallest $a_i$s are $a_1, \ldots, a_{2n+2}$

Let $v$ be the average of the $n$ largest $a_i$s. Let $x_i = v - a_i$ for each $i$. Then $3s = \ell + \sum_{i = 1}^{3n+2}a_i = \ell + \sum_{i = 1}^{2n+2}a_i + \sum_{i = 2n+2}^{3n+2}a_i = \ell + \sum_{i = 1}^{2n+2}(v - x_i) + nv = \ell + (3n+2)v - \sum_{i = 1}^{2n+2}(x_i) = (\ell-v) + (3n+3)v - \sum_{i = 1}^{2n+2}(x_i)$.

Then $s = (n+1)v + \frac{\ell - v}{3} - \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i)$.

If we choose some set $I$ of $n+1$ indices, then the sum of the $a_i$s with $i \in I$ is equal to $\sum_{i\in I}a_i=\sum_{i\in I}v - x_i = (n+1)v-\sum_{i\in I}x_i$. A set of indices $I$ is a valid choice for one of the groups provided this sum is at most $s$. In other words, using the alternate definition of $s$ derived above, the condition we are interested in is $\sum_{i\in I}x_i \ge \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i) - \frac{\ell - v}{3}$. Obviously, the remaining $n+1$ indices $I' = \{1,\ldots, 2n+2\} \setminus I$ must also satisfy this condition: $\sum_{i\in I'}x_i \ge \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i) - \frac{\ell - v}{3}$. Since $\sum_{i\in I'}x_i = \sum_{i = 1}^{2n+2}x_i - \sum_{i\in I}x_i$, we can rewrite the second condition as $\sum_{i\in I}x_i \le \frac{2}{3}\sum_{i = 1}^{2n+2}(x_i) + \frac{\ell - v}{3}$.

Thus we have restated this subproblem using an equivalent alternative: we are trying to choose a set $I$ of $n+1$ indices among $\{1, \ldots, 2n+2\}$ such that $\frac{2}{3}\sum_{i = 1}^{2n+2}(x_i) + \frac{\ell - v}{3} \ge \sum_{i\in I}x_i \ge \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i) - \frac{\ell - v}{3}$.

Note that $\ell \ge v$ (and therefore $\ell-v \ge 0$) since $v$ is the average of some $a_i$s and $\ell$ is an upper bound on all $a_i$s. Let $X = \sum_{i = 1}^{2n+2}(x_i)$. Our condition above can be rewritten as follows: choose a set $I$ of $n+1$ indices among $\{1, \ldots, 2n+2\}$ such that $\sum_{i\in I}x_i$ is in the interval $[cX, (1-c)X]$ where $c = \frac{1}{3} - \frac{\ell - v}{3X} \le \frac{1}{3}$.

Suppose that for some $j$, $x_j$ has value at least $\frac{X}{3}$. In this case, let $I$ consist of the index $j$ and also of the $n-1$ indices corresponding to the smallest $x_i$s. If these $x_i$s add to at most $(1-c)X$ then this choice of $I$ satisfies the above constraint: the sum $\sum_{i\in I}x_i$ is at least $x_j \ge \frac{X}{3} = \frac{1}{3}X \ge cX$ and at most $(1-c)X$. Thus, this set of indices $I$ can be used to select one of the groups of size $n+1$ in a solution to the packing problem instance. On the other hand, if these $x_i$s add to more than $(1-c)X$ then the instance cannot be solved: one of the two halves will include $x_j$ and the sum of that half is always going to be more than $(1-c)X$ (since it was more than that even when we put the smallest elements with $x_j$).

Thus, we have handled the case that some $x_j$ has value at least $\frac{X}{3}$. The remaining case is that every $x_i$ has value at most $\frac{X}{3}$. Then assign the $x_i$s to two groups, 1 and 2, arbitrarily. Create a matching of the elements of the two groups and swap those pairs one pair at a time. Over the course of this process, the sum of the elements of group 1 will move from it's initial sum to the initial sum of group 2's elements. In other words, the sum of group 1 will cross the average value $\frac{X}{2}$. Each step in this process involves group 1 losing an $x_i$ and gaining one; since the $x_i$s have value at most $\frac{X}{3}$, a pair of $x_i$s differs by at most $\frac{X}{3}$ and so each step moves the sum of group 1 by at most $\frac{X}{3}$. Thus, there will be some point in the process when the sum of group 1 is within half the maximum step size of the average. Thus, at some point the sum of group 1 will fall within $\frac{X}{2} \pm \frac{X}{6}$. But this is the interval $[\frac{1}{3}X, \frac{2}{3}X]$, which is a subinterval of $[cX, (1-c)X]$. Thus, at some point during this process, the group 1 at the time will satisfy our desired condition. We can use this group of $x_i$s to select a corresponding group of $a_i$s; these $a_i$s form one of the two groups of size $n+1$ needed to solve the packing problem instance.

Conclusion

The above exhaustive casework can be used as an algorithm to partition a list into three groups of the same sum using one soft number. The casework will also identify when this is impossible. The runtime of this algorithm is polynomial.

$\endgroup$
  • $\begingroup$ Thanks! Lemma 1 proof can be shortened: order group 2's elements by increasing order. Let group 2a be the odd-indexed elements and group 2b the even-indexed elements. Each element in 2a is smaller than the next element which is in 2b, so $S_{2b} \geq S_{2a}$. On the other hand, if we remove the smallest element from 2a and the largest element from 2b, the sum of elements remaining in 2a is at least the sum of elements remaining in 2b. So $S_{2b}-S_{2a}\leq$ the largest minus smallest element = $l/2$. By the assumption, $S_{2b}+S_{2a}\leq 2s-l/2$. Summing the inequalities gives $S_{2b}\leq s$. $\endgroup$ – Erel Segal-Halevi Feb 5 at 17:03
  • $\begingroup$ Question: you mention a sub-problem: "is it possible to partition the $2n+2$ smallest $a_i$-s into two groups of size $n+1$ such that each of those two groups has sum at most $s$?". Why is this problem not as hard as the PARTITION problem? $\endgroup$ – Erel Segal-Halevi Feb 5 at 17:06
  • $\begingroup$ You're right, my Lemma 1 proof is not the simplest possible. I'm a bit too lazy to put in the edits though (especially since other parts of the proof reference the techniques used in the proof). As for the sub-problem, the reason it is not as hard as PARTITION is that you don't actually have to solve that subproblem in full generality: the value of $s$ is not arbitrary. In order to fall into that case, there are specific additional constraints on $s$ and on the $a_i$s that must hold. If these constraints were missing, you would be right: the problem would be as hard as PARTITION. $\endgroup$ – Mikhail Rudoy Feb 5 at 17:13
  • $\begingroup$ Thanks a lot for the clear and detailed solution. $\endgroup$ – Erel Segal-Halevi Feb 6 at 22:37
  • $\begingroup$ Hi Mikhail, we are working on a paper in which this result is useful. Would you like to join? If so then please write me an email. $\endgroup$ – Erel Segal-Halevi Apr 18 at 4:36
3
$\begingroup$

This answer does not solve the question. It only settles the following auxiliary problem formulated by @JohnDvorak in the comments (partitioning a set in 1:2 ratio):

Auxiliary problem:
Instance: Positive rationals $a_1,\ldots,a_m$ with $\sum_{i=1}^m a_i = 3A$.
Question: Does there exist an index set $I\subseteq\{1,\ldots,n\}$ with $\sum_{i\in I}a_i=A$?

  • Take an instance of classical PARTITION (rationals $b_1,\ldots,b_n$ with sum $2B$, can you split them into two groups with sum $B$).
  • Take $b_1,\ldots,b_n$ together with the four numbers $5B,5B,5B,7B$ to create an instance of the auxiliary problem. The sum of all $n+4$ numbers then is $24B$, so that $A=8B$.
  • Splitting the $n+4$ numbers into a group with sum $A=8B$ and a group with sum $2A=16B$ is possible if and only if the PARTITION instance has answer YES.

Hence @JohnDvorak's auxiliary problem is NP-complete

$\endgroup$
  • $\begingroup$ Hi Gamow, we are working on a paper in which this result may be useful. Would you like to join? If so then please write me an email. $\endgroup$ – Erel Segal-Halevi Apr 18 at 7:26

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.