{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:47:25Z","timestamp":1770994045954,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540405344","type":"print"},{"value":"9783540450719","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45071-8_36","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T08:04:43Z","timestamp":1193472283000},"page":"351-363","source":"Crossref","is-referenced-by-count":40,"title":["Tetris is Hard, Even to Approximate"],"prefix":"10.1007","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Susan","family":"Hohenberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Liben-Nowell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,24]]},"reference":[{"key":"36_CR1","unstructured":"R. Breukelaar, H. J. Hoogeboom, and W. A. Kosters. Tetris is hard, made easy. Technical report, Leiden Institute of Advanced Computer Science, 2003."},{"key":"36_CR2","unstructured":"J. Brzustowski. Can you win at Tetris? Master\u2019s thesis, U. British Columbia, 1992."},{"key":"36_CR3","doi-asserted-by":"crossref","unstructured":"H. Burgiel. How to lose at Tetris. Mathematical Gazette, July 1997.","DOI":"10.2307\/3619195"},{"key":"36_CR4","doi-asserted-by":"crossref","unstructured":"E. D. Demaine. Playing games with algorithms: Algorithmic combinatorial game theory. In Proc. MFCS, pages 18\u201332, August 2001. cs.CC\/0106019.","DOI":"10.1007\/3-540-44683-4_3"},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"E. D. Demaine, S. Hohenberger, and D. Liben-Nowell. Tetris is hard, even to approximate. Technical Report MIT-LCS-TR-865, 2002. cc.CC\/0210020.","DOI":"10.1007\/3-540-45071-8_36"},{"key":"36_CR6","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"M. R. Garey","year":"1975","unstructured":"M. R. Garey and D. S. Johnson. Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput., 4:397\u2013411, 1975.","journal-title":"SIAM J. Comput."},{"key":"36_CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979."},{"issue":"2","key":"36_CR8","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/BF03025367","volume":"22","author":"R. Kaye","year":"2000","unstructured":"R. Kaye. Minesweeper is NP-Complete. Math. Intelligencer, 22(2):9\u201315, 2000.","journal-title":"Math. Intelligencer"},{"key":"36_CR9","unstructured":"S. Kim. Tetris unplugged. Games Magazine, pages 66\u201367, July 2002."},{"key":"36_CR10","series-title":"Technical Report","volume-title":"Multiple objective solution for Tetris","author":"M. M. Kostreva","year":"1999","unstructured":"M. M. Kostreva and R. Hartman. Multiple objective solution for Tetris. Technical Report 670, Department of Mathematical Sciences, Clemson U., May 1999."},{"key":"36_CR11","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/0022-0000(85)90045-5","volume":"31","author":"C. Papadimitriou","year":"1985","unstructured":"C. Papadimitriou. Games against nature. J. Comp. Sys. Sci., 31:288\u2013301, 1985.","journal-title":"J. Comp. Sys. Sci."},{"key":"36_CR12","volume-title":"Game Over: Nintendo\u2019s Battle to Dominate an Industry","author":"D. Sheff","year":"1993","unstructured":"D. Sheff. Game Over: Nintendo\u2019s Battle to Dominate an Industry. Hodder and Stoughton, London, 1993."},{"key":"36_CR13","unstructured":"Tetris, Inc. http:\/\/www.tetris.com."},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"U. Zwick. Jenga. In Proc. SODA, pages 243\u2013246, 2002.","DOI":"10.1201\/9781420040487-20"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45071-8_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,26]],"date-time":"2021-08-26T09:35:49Z","timestamp":1629970549000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45071-8_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405344","9783540450719"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45071-8_36","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]}}}