3-partition problem: Difference between revisions

Revision as of 09:23, 2 February 2024

Revision as of 22:29, 3 February 2024

Line 29:

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 ''S_r'' of the restricted variant, with 3''m'' items summing up to ''mT'', construct a new instance of the unrestricted variant {{math|''S_u'' ≔ {s + 2''T'' {{!}} s ∈ ''S_r''}}}, with 3m items summing up to 7mT, and with target sum 7{{hsp|''T''}}. Every solution of ''S_r'' naturally corresponds to a solution of ''S_u''. Conversely, in every solution of ''S_u'', since the target sum is 7{{hsp|''T''}} and each element is in {{nowrap|{{pars|{{hsp|''T''}}/4, 7{{hsp|''T''}}/2}}}}, there must be exactly 3 elements per set, so it corresponds to a solution of ''S_r''.

The '''ABC-partition problem''' (also called '''[[Numerical 3-dimensional matching|numerical 3-d matching]])''' is a variant in which, instead of a set ''S'' with 3{{hsp|''m''}} integers, there are three sets ''A'', ''B'', ''C'' with ''m'' integers in each. The sum of numbers in all sets is {{tmath|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 |archive-url=https://ghostarchive.org/varchive/youtube/20211214/ZaSMm2xvatw |archive-date=2021-12-14 |url-status=live|website=Youtube}}{{cbignore}}</ref>

* 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 {{tmath|A, B, C}}, where there is an hyperedge {{tmath|(a, b, c)}} for every three vertices in {{tmath|A, B, C}} such that <math>a+b+c = T</math>. A matching in this hypergraph corresponds to a solution to ABC-partition.

The '''4-partition problem''' is a variant in which ''S'' contains ''n'' = 4{{hsp|''m''}} integers, the sum of all integers is {{tmath|m T}}, and the goal is to partition it into ''m'' quadruplets, all with a sum of ''T''. It can be assumed that each integer is strictly between ''T''/5 and ''T''/3. Similarly, '''ABCD-parititon''' is a variant of 4-partition in which each there are 4 input sets and each quadruplet should contain one element from each set.