Partition problem

The partition problem (also number distribution problem, often noted with PARTITION ) is an optimization or decision problem in combinatorics .

Formulation of the partition problem

The task for the partition problem is: Given a ( multi- ) set of natural numbers. We are looking for a division of these numbers into two piles so that the difference between the sums of the numbers in the two piles is as small as possible.

An equivalent formulation reads more precisely: A (multi-) set A of N natural numbers is given . We are looking for a subset such that ${\ displaystyle a_ {i}}$ ${\ displaystyle A_ {1} \ subset A}$

${\ displaystyle E: = \ left | \ sum _ {a_ {i} \ in A_ {1}} a_ {i} - \ sum _ {a_ {i} \ in A \ setminus A_ {1}} a_ {i } \ right |}$

becomes minimal. A division for which is called a perfect division. ${\ displaystyle E = 0}$

As an additional condition, one can restrict the solution set of the partition problem from the start by only permitting balanced partitions in which both clusters are equal, i.e. the number of numbers in the subsets must be the same for even N and must be equal for odd N. differ by 1. In this case too, the partition problem is complete. ${\ displaystyle {\ mathcal {NP}}}$

If you change the question and ask, "Is there a perfect division?", The optimization problem described above becomes a decision problem . One is no longer looking for the best distribution, but only asks about its existence.

The partition problem is one of the 21 classic NP-complete problems , of which Richard M. Karp was able to show in 1972 that they belong to the class of NP-complete problems.

Phase transition in the partition problem

One observes two different so-called phases with the partition problem: If the set A consists of many small numbers, it is clear that there are many perfect partitions, and it is easy to find one of these partitions (simple phase). On the other hand, if A consists of a few large numbers, it is unlikely that a perfect division exists at all, and you have to try out all the possibilities to find the best division (hard phase).

Between the simple and the hard phase, a phase transition, the one in analogy to the statistical physics phase transition called. At this phase transition, the probability of finding a perfect distribution drops by leaps and bounds from 1 in the easy phase to 0 in the hard phase. As the number N of numbers increases, the transition becomes sharper.

The position of the phase transition depending on the number and size of the individual numbers can be calculated using methods of statistical physics .

All currently known algorithms have a “worst-case runtime” that grows exponentially with the number of numbers N , that is, in the worst case, it needs computing time that increases exponentially with N to solve the decision problem . In many cases, however, the computing time actually required is significantly less: In the simple phase, the algorithm quickly comes across one of the many perfect solutions and can therefore answer the decision problem with “yes, there is a perfect solution” and stop the search. Even in the hard phase, suitable algorithms (e.g. the cBLDM algorithm) can quickly end the search with a negative decision if no solution exists. The "most difficult" problems are therefore directly at the phase transition, where all the subdivisions have to be tried out before the problem can be decided. ${\ displaystyle 2 ^ {N-1}}$

Solution through dynamic programming

With the help of dynamic programming one can solve the partition problem in pseudopolynomial time . Smaller sub-problems are systematically examined and their solutions tabulated and recursively combined.

Let be the sum of all given numbers. If it is odd, there is obviously no perfect split. Otherwise it is checked for all and all whether there is a selection of numbers in the family of the first numbers, the sum of which is exactly . For and this is obviously the case, just as for and . For and not for all others . This is the beginning of the recursion, which is noted in the first row of a table. For the other lines, the entries result from the following recursion: A selection for exists exactly if either one for already exists, or if is and a selection for exists. The last entry in the table (for and ) gives the answer to the decision problem . ${\ displaystyle S}$ ${\ displaystyle 0 \ leq i \ leq N}$ ${\ displaystyle 0 \ leq j \ leq S / 2}$ ${\ displaystyle \ {a_ {1}, a_ {2}, ..., a_ {i} \}}$ ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle i = 0}$ ${\ displaystyle j = 0}$ ${\ displaystyle i = 1}$ ${\ displaystyle j = a_ {1}}$ ${\ displaystyle i> 1}$ ${\ displaystyle j}$ ${\ displaystyle (i, j)}$ ${\ displaystyle (i-1, j)}$ ${\ displaystyle j> a_ {i}}$ ${\ displaystyle (i-1, y-a_ {i})}$ ${\ displaystyle i = N}$ ${\ displaystyle j = S / 2}$

The complexity of this algorithm is . ${\ displaystyle {\ mathcal {O}} (n \ cdot S)}$

literature

Steven S. Skiena: The Algorithm Design Manual. Corrected 2nd printing. Springer et al., New York NY et al. 1998, ISBN 0-387-94860-0 .

Individual evidence

↑ Michael R. Garey, David Stifler Johnson : Computers and Intractability . A Guide to the Theory of NP Completeness. ISBN 0-7167-1045-5 , pp. 223 .
↑ Michael R. Garey, David Stifler Johnson : Computers and Intractability . A Guide to the Theory of NP Completeness. ISBN 0-7167-1045-5 , pp. 47 .
↑ S. Mertens: A complete anytime algorithm for balanced number partitioning , arxiv : cs / 9903011
↑ Michael R. Garey, David Stifler Johnson : Computers and Intractability . A Guide to the Theory of NP Completeness. ISBN 0-7167-1045-5 , pp. 90-92 .

[1] Michael R. Garey, David Stifler Johnson : Computers and Intractability . A Guide to the Theory of NP Completeness. ISBN 0-7167-1045-5 , pp. 223 .

[2] Michael R. Garey, David Stifler Johnson : Computers and Intractability . A Guide to the Theory of NP Completeness. ISBN 0-7167-1045-5 , pp. 47 .

[npp5-3] S. Mertens: A complete anytime algorithm for balanced number partitioning , arxiv : cs / 9903011

[4] Michael R. Garey, David Stifler Johnson : Computers and Intractability . A Guide to the Theory of NP Completeness. ISBN 0-7167-1045-5 , pp. 90-92 .