3-PARTITION Problem

Question

here is another question about dynamic programming ( Vazirani ch6 )

Consider the following 3-PART problem. For integers a1 ... an, we want to determine whether it is possible to partition {1 ... n} into three disjoint subsets I, J, K such that

sum (I) = sum (J) = sum (K) = 1/3 * sum (ALL)

For example, to enter (1; 2; 3; 4; 4; 5; 8), the answer is yes, because there is a partition (1; 8), (4; 5), (2; 3; 4). On the other hand, for input (2; 2; 3; 5) the answer is no. develop and analyze dynamic programming algorithm for 3-PARTITION, which works in a polynomial of time in n and (Sum a_i)

How can I solve this problem? I know a 2-section, but still can not solve it.

Answer 1

It is easy to generalize the solution of two sets for the case of three sets.

In the original version, you create an array of boolean sums , where sums[i] indicates whether sum i with numbers from the set can be reached or not. Then, once the array is created, you just see if sums[TOTAL/2] true or not.

Since you said that you know the old version, I will only describe the difference between them.

In the case of 3 sections, you save an array of boolean sums , where sums[i][j] indicates whether the first set can have the sum i and second-sum j . Then, as soon as the array is created, you just see if sums[TOTAL/3][TOTAL/3] true or not.

If the original complexity is O(TOTAL*n) , here it is O(TOTAL^2*n) .
It cannot be polynomial in the strict sense of the word, but then the original version is also not strictly polynomial :)

Answer 2

I think with the help of reduction this happens as follows:

Reducing a 2-section to a 3-section:

Let S be the original set and A its total sum, then S '= the union ({A / 2}, S). Therefore, to perform a 3-partition on the set S 'gives three sets X, Y, Z. Among X, Y, Z, one of them must be {A / 2}, say, the set Z, then X and Y is a 2-partition. Witnesses of a 3-partition on S 'are witnesses of a 2-partition on S; therefore, a 2-partition reduces to a 3-partition.

Answer 3

If this problem should be solvable; then sum(ALL)/3 must be an integer. Any solution should have SUM(J) + SUM(K) = SUM(I) + sum(ALL)/3 . This is a solution to the 2-partition problem over concat(ALL, {sum(ALL)/3}) .

You say that you have an implementation with two sections: use it to solve this problem. Then (at least) one of the two sections will contain the number sum(ALL)/3 - remove the number from this partion, and you find I For another partition, run the 2 partition again to share J with K ; after all, J and K must be equal on their own.

Edit: This solution is probably incorrect - a 2-bit concatenated set will have several solutions (at least one for each of I, J, K), however, if there are other solutions, then the "other side" may not consist of a union two of I, J, K and generally cannot be splittable. You will need to think, I'm afraid :-).

Try 2: Iterating over a multiset, keeping the following map: R(i,j,k) :: Boolean , which represents the fact that prior to the current iteration, numbers allow division into three multisets that have sums I , J , K Ie For any R(i,j,k) and the next number n in the next state R' it contains R'(i+n,j,k) and R'(i,j+n,k) and R'(i,j,k+n) . Note that the complexity (in accordance with the examination) depends on the value of the input numbers; it is a pseudopolynomial time algorithm. Nikita's solution is conceptually similar, but more efficient than this, because it does not track the third set amount: it is unnecessary, because you can trivially calculate it.

Answer 4

Suppose you want to split the partition set $X = {x_1, ..., x_n}$ into $k$ . Create a table $ n \ times k $. Assume that the cost of $M[i,j]$ will be the maximum sum of elements of $i$ in $ j $ sections. Use the following optimality criterion recursively to populate it:

 M[n,k] = min_{i\leq n} max ( M[i, k-1], \sum_{j=i+1}^{n} x_i ) Using these initial values for the table: M[i,1] = \sum_{j=1}^{i} x_i and M[1,j] = x_j The running time is $O(kn^2)$ (polynomial ) 

Answer 5

You really need the Korf Complete Karmarkar-Karp algorithm ( http://ac.els-cdn.com/S0004370298000861/1-s2.0-S0004370298000861-main.pdf , http://ijcai.org/papers09/Papers/IJCAI09- 096.pdf ). A generalization to three parts is given. The algorithm is surprisingly fast, given the complexity of the problem, but requires some implementation.

The essential idea of ​​KK is to ensure that large blocks of the same size are displayed in different sections. One group of pairs of blocks, which can then be considered as a smaller block of size equal to the difference in sizes that can be placed as usual: in a recursive way, each ending in small blocks that are easy to place. Block groups are then split twice to provide access to opposing placements. Expanding to a 3-section is a bit more complicated. The Korf extension should use a depth search in the KK order to find all possible solutions or quickly find a solution.