3-partition problem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

The 3-partition problem is a strongly NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triplets that all have the same sum. More precisely:

  • The input to the problem is a multiset S of n = 3 m positive integers. The sum of all integers is m T.
  • The output is whether or not there exists a partition of S into m triplets S1, S2, …, Sm such that the sum of the numbers in each one is equal to T. The S1, S2, …, Sm must form a partition of S in the sense that they are disjoint and they cover S.

The 3-partition problem remains strongly NP-complete under the restriction that every integer in S is strictly between T/4 and T/2.

Example[edit]

The set S = { 20, 23, 25, 30, 49, 45, 27, 30, 30, 40, 22, 19 } can be partitioned into the four sets { 20, 25, 45 }, { 23, 27, 40 }, { 49, 22, 19 } , { 30, 30, 30}, each of which sum to T = 90. Another example; the set S = {1, 2, 5, 6, 7, 9} can be partitioned into the two sets {1, 5, 9}, {2, 6, 7} each of which sum to T = 15.

Strong NP-completeness[edit]

The 3-partition problem remains NP-complete even when the integers in S are bounded above by a polynomial in n. In other words, the problem remains NP-complete even when representing the numbers in the input instance in unary. i.e., 3-partition is NP-complete in the strong sense or strongly NP-complete. This property, and 3-partition in general, is useful in many reductions where numbers are naturally represented in unary.

3-Partition vs Partition[edit]

The 3-partition problem is similar to the partition problem, in which the goal is to partition S into two subsets with equal sum, and the multiway number partitioning, in which the goal is to partition S into k subsets with equal sum, where k is a fixed parameter. In 3-Partition the goal is to partition S into m = n/3 subsets, not just a fixed number of subsets, with equal sum. Partition is "easier" than 3-Partition: while 3-Partition is strongly NP-hard, Partition is only weakly NP-hard - it is hard only when the numbers are encoded in non-unary system, and have value exponential in n. When the values are polynomial in n, Partition can be solved in polynomial time using the pseudopolynomial time number partitioning algorithm.

Variants[edit]

In the unrestricted-input variant, the inputs can be arbitrary integers; in the restricted-input variant, the inputs must be in (T/4 , T/2). The restricted version is as hard as the unrestricted version: given an instance Su of the unrestricted variant, construct a new instance of the restricted version Sr := {s + 2 T | s in Su}. Every solution of Su corresponds to a solution of Sr but with a sum of 7 T instead of T, and every element of Sr is in [2 T, 3 T] which is contained in (7 T / 4, 7 T / 2).

In the distinct-input variant, the inputs must be in (T/4 , T/2), and in addition, they must all be distinct integers. It, too, is as hard as the unrestricted version.[1]

In the unrestricted-output variant, the m output subsets can be of arbitrary size - not necessarily 3 (but they still need to have the same sum T). The restricted-output variant can be reduced to the unrestricted-variant: given an instance Su of the restricted variant, construct a new instance of the unrestricted variant Sr := {s + 2 T | s in Su}, with target sum 7 T. Every solution of Su naturally corresponds to a solution of Sr. In every solution of Sr, since the target sum is 7 T and each element is in (7 T / 4, 7 T / 2), there must be exactly 3 elements per set, so it corresponds to a solution of Su.

The 4-partition problem is a variant in which S contains n = 4 m integers, the sum of all integers is m T, and the goal is to partition it into m quadruples, all with a sum of T. It can be assumed that each integer is strictly between T/5 and T/3.

The ABC-partition problem is a variant in which, instead of a set S with 3 m integers, there are three sets A, B, C with m integers in each. The sum of numbers in all sets is m T. The goal is to construct m triplets, each of which contains one element from A, one from B and one from C, such that the sum of each triplet is T. [2] This problem can be reduced to 3-partition as follows. Construct a set S containing the numbers 1000a+100 for each a in A; 1000b+10 for each b in B; and 1000c+1 for each c in C. Every solution of the ABC-partition instance induces a solution of the 3-partition instance with sum 1000(a+b+c)+111 = 1000T+111. Conversely, in every solution of the 3-partition instance, all triplet-sums must have the same hundreds, tens and units digits, which means that they must have exactly 1 in each of these digits. Therefore, each triplet must have exactly one number of the form 1000a+100, one 1000b+10 and one 1000c+1. Hence, it induces a solution to the ABC-partition instance.

  • The ABC-partition problem is also called numerical 3-d matching, as it can also be reduced to the 3-dimensional matching problem: given an instance of ABC-partition, construct a tripartite hypergraph with sides A, B, C, where there is an hyperedge (a, b, c) for every three vertices in A, B, C such that a+b+c = T. A matching in this hypergraph corresponds to a solution to ABC-partition.

Proofs[edit]

Garey and Johnson (1975) originally proved 3-Partition to be NP-complete, by a reduction from 3-dimensional matching.[3] The classic reference by Garey and Johnson (1979) describes an NP-completeness proof, reducing from 3-dimensional matching to 4-partition to 3-partition.[4]

Applications[edit]

The NP-hardness of 3-partition was used to prove the NP-hardness rectangle packing, as well as of Tetris[5][6] and some other puzzles,[7] and some job scheduling problems.[8]

References[edit]

  1. ^ Hulett, Heather; Will, Todd G.; Woeginger, Gerhard J. (2008-09-01). "Multigraph realizations of degree sequences: Maximization is easy, minimization is hard". Operations Research Letters. 36 (5): 594–596. doi:10.1016/j.orl.2008.05.004. ISSN 0167-6377.
  2. ^ Demaine, Erik (2015). "MIT OpenCourseWare - Hardness made Easy 2 - 3-Partition I". Youtube.
  3. ^ Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5. Pages 96–105 and 224.
  4. ^ Garey, Michael R. and David S. Johnson (1975). "Complexity results for multiprocessor scheduling under resource constraints". SIAM Journal on Computing. 4 (4): 397–411. doi:10.1137/0204035.
  5. ^ "Tetris is hard, even to approximate". Nature. 2002-10-28. doi:10.1038/news021021-9. ISSN 0028-0836.
  6. ^ BREUKELAAR, RON; DEMAINE, ERIK D.; HOHENBERGER, SUSAN; HOOGEBOOM, HENDRIK JAN; KOSTERS, WALTER A.; LIBEN-NOWELL, DAVID (2004-04-01). "Tetris is Hard, Even to Approximate". International Journal of Computational Geometry & Applications. 14 (1n02): 41–68. arXiv:cs/0210020. doi:10.1142/s0218195904001354. ISSN 0218-1959.
  7. ^ Demaine, Erik D.; Demaine, Martin L. (2007-06-01). "Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity". Graphs and Combinatorics. 23 (S1): 195–208. doi:10.1007/s00373-007-0713-4. ISSN 0911-0119.
  8. ^ Bernstein, D.; Rodeh, M.; Gertner, I. (1989). "On the complexity of scheduling problems for parallel/pipelined machines". IEEE Transactions on Computers. 38 (9): 1308–1313. doi:10.1109/12.29469. ISSN 0018-9340.