3-partition problem: Difference between revisions

Revision as of 18:48, 7 December 2020

Revision as of 02:01, 14 December 2020

Line 27:

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''. <ref>{{Cite web|last=Demaine|first=Erik|date=2015|title=MIT OpenCourseWare - Hardness made Easy 2 - 3-Partition I|url=https://www.youtube.com/watch?v=ZaSMm2xvatw|url-status=live|archive-url=|archive-date=|access-date=|website=Youtube}}</ref> This problem can be reduced to 3-partition as follows. Construct a set S containing the numbers 1000''a''+100 for each ''a'' in A; 1000''b''+10 for each ''b'' in B; and 1000''c''+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 = 1000''T''+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 1000''a''+100, one 1000''b''+10 and one 1000''c''+1. Hence, it induces a solution to the ABC-partition instance.

* The ABC-partition problem is also called '''[[Numerical 3-dimensional matching|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.

Line 35:

== Applications ==

The NP-hardness of 3-partition was used to prove the NP-hardness [[rectangle packing]], as well as of [[Tetris]]<ref>{{Cite journal|date=2002-10-28|title=Tetris is hard, even to approximate|url=http://dx.doi.org/10.1038/news021021-9|journal=Nature|doi=10.1038/news021021-9|issn=0028-0836}}</ref><ref>{{Cite journal|last=BREUKELAAR|first=RON|last2=DEMAINE|first2=ERIK D.|last3=HOHENBERGER|first3=SUSAN|last4=HOOGEBOOM|first4=HENDRIK JAN|last5=KOSTERS|first5=WALTER A.|last6=LIBEN-NOWELL|first6=DAVID|date=2004-04-01|title=TETRIS IS HARD, EVEN TO APPROXIMATE|url=http://dx.doi.org/10.1142/s0218195904001354|journal=International Journal of Computational Geometry & Applications|volume=14|issue=01n02|pages=41–68|doi=10.1142/s0218195904001354|issn=0218-1959|via=}}</ref> and some other puzzles,<ref>{{Cite journal|last=Demaine|first=Erik D.|last2=Demaine|first2=Martin L.|date=2007-06-01|title=Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity|url=http://dx.doi.org/10.1007/s00373-007-0713-4|journal=Graphs and Combinatorics|volume=23|issue=S1|pages=195–208|doi=10.1007/s00373-007-0713-4|issn=0911-0119|via=}}</ref> and some [[Job scheduling|job scheduling problems]].<ref>{{Cite journal|last=Bernstein|first=D.|last2=Rodeh|first2=M.|last3=Gertner|first3=I.|date=1989|title=On the complexity of scheduling problems for parallel/pipelined machines|url=http://dx.doi.org/10.1109/12.29469|journal=IEEE Transactions on Computers|volume=38|issue=9|pages=1308–1313|doi=10.1109/12.29469|issn=0018-9340}}</ref>

==References==