3-partition problem: Difference between revisions

Revision as of 04:51, 3 January 2023

Revision as of 07:06, 26 April 2023

Line 22:

==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 ''S_u'' of the unrestricted variant, construct a new instance of the restricted version {{math|''S<spansub>r</sub>'' ≔ {s + 2{{hsp|''T''}} {{!}} s &isin; ''S_u''}}}. Every solution of ''S_u'' corresponds to a solution of ''S_r'' but with a sum of 7{{hsp|''T''}} instead of ''T'', and every element of ''S_r'' is in {{nowrap|[2{{hsp|''T''}}, 3{{hsp|''T''}}]}} which is contained in {{nowrap|{{pars|{{hsp|''T''}}/4, 7{{hsp|''T''}}/2}}}}. class=

"texhtml">''S_r'' ≔ {s + 2{{hsp|''T''}} | s &isin; ''S_u''}</span>. Every solution of ''S_u'' corresponds to a solution of ''S_r'' but with a sum of 7{{hsp|''T''}} instead of ''T'', and every element of ''S_r'' is in {{nowrap|[2{{hsp|''T''}}, 3{{hsp|''T''}}]}} which is contained in {{nowrap|{{pars|{{hsp|''T''}}/4, 7{{hsp|''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.<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_u'' of the restricted variant, construct a new instance of the unrestricted variant {{math|''S<spansub>r</sub>'' ≔ {s + 2{{hsp{{!}}''T''}} {{!}} s &isin; ''S_u''}}}, with target sum 7{{hsp|''T''}}. Every solution of ''S_u'' naturally corresponds to a solution of ''S_r''. In every solution of ''S_r'', 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_u''. class=

"texhtml">''S_r'' ≔ {s + 2{{hsp|''T''}} | s &isin; ''S_u''}</span>, with target sum 7{{hsp|''T''}}. Every solution of ''S_u'' naturally corresponds to a solution of ''S_r''. In every solution of ''S_r'', 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_u''.

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.