Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) →Variants: Thanks to Juho https://cs.stackexchange.com/a/60320/1342 |
||
Line 20:
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 ''S<sub>r</sub>'' := {s + 2 ''T'' | s in ''S<sub>u</sub>''}. Every solution of ''S<sub>u</sub>'' corresponds to a solution of ''S<sub>r</sub>'' but with a sum of 7 ''T'' instead of ''T'', and every element of ''S<sub>r</sub>'' 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.<ref>{{Cite journal|last=Hulett|first=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 ''S<sub>r</sub>'' := {s + 2 ''T'' | s in ''S<sub>u</sub>''}, with target sum 7 ''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 ''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 ''S<sub>u</sub>''.
| |||