3-partition problem: Difference between revisions

Content deleted Content added
Line 35:
 
== Applications ==
The NP-hardness of 3-partition was used to prove the NP-hardness [[rectangle packing]], as well as of [[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}}</ref><ref>{{Cite journal|last=BREUKELAAR|first=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|date=2004-04-01|title=TETRIS IS HARD, EVEN TO APPROXIMATE|url=http://dx.doi.org/10.1142/s0218195904001354|journal=International Journal of Computational Geometry & Applications|volume=14|issue=01n02|pages=41–68|doi=10.1142/s0218195904001354|issn=0218-1959|via=}}</ref> as well as ofand some other puzzles,<ref>{{Cite journal|last=Demaine|first=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|issn=0911-0119|via=}}</ref> and some [[Job scheduling|job scheduling problem]]<nowiki/>s.<ref>{{Cite journal|last=Bernstein|first=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}}</ref>
 
==References==