3-partition problem

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

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

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

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

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 hunderds, 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

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

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
  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 (01n02): 41–68. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.