Content deleted Content added
Citation bot (talk | contribs) Alter: title, issue. Add: authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform |
m Add more specific reference to Tetris page |
||
Line 35:
== 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}}</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}}</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|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}}</ref>
==References==
| |||