Content deleted Content added
Fixed Grammer in problem overview |
m Open access bot: url-access updated in citation with #oabot. |
||
Line 26:
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 {{math|''S<sub>r</sub>'' ≔ {s + 2{{hsp|''T''}} {{!}} s ∈ ''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{{hsp|''T''}} instead of ''T'', and every element of ''S<sub>r</sub>'' 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|url-access=subscription}}</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>r</sub>'' of the restricted variant, with 3''m'' items summing up to ''mT'', construct a new instance of the unrestricted variant {{math|''S<sub>u</sub>'' ≔ {s + 2''T'' {{!}} s ∈ ''S<sub>r</sub>''}}}, with 3m items summing up to 7mT, and with target sum 7{{hsp|''T''}}. Every solution of ''S<sub>r</sub>'' naturally corresponds to a solution of ''S<sub>u</sub>''. Conversely, in every solution of ''S<sub>u</sub>'', 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<sub>r</sub>''.
Line 92:
== Applications ==
The NP-hardness of 3-partition was used to prove the NP-hardness [[rectangle packing]], as well as of [[Tetris#Computational complexity|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|url-access=subscription}}</ref><ref>{{Cite journal|last1=BREUKELAAR|first1=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|title=Tetris is Hard, Even to Approximate|date=2004-04-01|url=http://dx.doi.org/10.1142/s0218195904001354|journal=International Journal of Computational Geometry & Applications|volume=14|issue=1n02|pages=41–68|doi=10.1142/s0218195904001354|issn=0218-1959|arxiv=cs/0210020|s2cid=1177 }}</ref> and some other puzzles,<ref>{{Cite journal|last1=Demaine|first1=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|s2cid=17190810 |issn=0911-0119}}</ref> and some [[Job scheduling|job scheduling problems]].<ref>{{Cite journal|last1=Bernstein|first1=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|url-access=subscription}}</ref>
==References==
| |||