|
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 ''S<sub>u</sub>'' of the unrestricted variant, construct a new instance of the restricted version <span class=
"texhtml">''S<sub>r</sub>'' :=≔ {s + 2{{gaps|2hsp|''T''}} | s ∈ ''S<sub>u</sub>''}</span>. Every solution of ''S<sub>u</sub>'' corresponds to a solution of ''S<sub>r</sub>'' but with a sum of 7 {{hsp|''T''}} instead of ''T'', and every element of ''S<sub>r</sub>'' is in {{mathnowrap|[2{{gaps|2hsp|''T''}}, 3{{gaps|3hsp|''T''}}]}} which is contained in {{mathnowrap|{{pars|{{sfrac|{{gaps|7hsp|''T''}}|/4}}, 7{{sfrachsp|{{gaps|7| ''T''}}|/2}}|150%}}}}.
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.<ref>{{Cite journal|last1=Hulett|first1=Heather|last2=Will|first2=Todd G.|last3=Woeginger|first3=Gerhard J.|date=2008-09-01|title=Multigraph realizations of degree sequences: Maximization is easy, minimization is hard|url=http://www.sciencedirect.com/science/article/pii/S0167637708000552|journal=Operations Research Letters|language=en|volume=36|issue=5|pages=594–596|doi=10.1016/j.orl.2008.05.004|issn=0167-6377}}</ref>
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<sub>u</sub>'' of the restricted variant, construct a new instance of the unrestricted variant <span class=
"texhtml">''S<sub>r</sub>'' :=≔ {s + 2{{gaps|2hsp|''T''}} | s ∈ ''S<sub>u</sub>''}</span>, with target sum 7 {{hsp|''T''}}. Every solution of ''S<sub>u</sub>'' naturally corresponds to a solution of ''S<sub>r</sub>''. In every solution of ''S<sub>r</sub>'', since the target sum is 7 {{hsp|''T''}} and each element is in {{mathnowrap|{{pars|{{sfrac|{{gaps|7hsp|''T''}}|/4}}, 7{{sfrachsp|{{gaps|7| ''T''}}|/2}}|150%}}}}, there must be exactly 3 elements per set, so it corresponds to a solution of ''S<sub>u</sub>''.
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'' 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 {{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> This problem can be reduced to 3-partition as follows. Construct a set S containing the numbers {{gaps|1000''a''|+|100}} for each ''{{tmath|a'' \in A}}; {{gaps|1000''b''|+|10}} for each ''{{tmath|b'' \in B}}; and {{gaps|1000''c''|+|1}} for each ''{{tmath|c'' \in C}}. Every solution of the ABC-partition instance induces a solution of the 3-partition instance with sum <math>1000(a+b+c)+111 = 1000T+111</math>. 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 {{gaps|1000''a''|+|100}}, one {{gaps|1000''b''|+|10}} and one {{gaps|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 {{tmath|A, B, C}}, where there is an hyperedge <math>{{tmath|(a, b, c)</math>}} 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.
== Proofs ==
|
