{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:26:57Z","timestamp":1743038817879,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030648428"},{"type":"electronic","value":"9783030648435"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-64843-5_36","type":"book-chapter","created":{"date-parts":[[2020,12,4]],"date-time":"2020-12-04T16:04:24Z","timestamp":1607097864000},"page":"530-544","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Cutting Stock with Rotation: Packing Square Items into Square Bins"],"prefix":"10.1007","author":[{"given":"Shahin","family":"Kamali","sequence":"first","affiliation":[]},{"given":"Pooya","family":"Nikbakht","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,12,4]]},"reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamsen, M., Miltzow, T., Seiferth, N.: Framework for $$exists$$r-completeness of two-dimensional packing problems. CoRR 2004.07558 (2020)","DOI":"10.1109\/FOCS46700.2020.00098"},{"issue":"2","key":"36_CR2","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1137\/S0097539797324874","volume":"29","author":"S Albers","year":"1999","unstructured":"Albers, S.: Better bounds for online scheduling. SIAM J. Comput. 29(2), 459\u2013473 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"36_CR3","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1007\/s00453-016-0172-5","volume":"78","author":"S Albers","year":"2017","unstructured":"Albers, S., Hellwig, M.: Online makespan minimization with parallel schedules. Algorithmica 78(2), 492\u2013520 (2017)","journal-title":"Algorithmica"},{"key":"36_CR4","unstructured":"Allen, S.R., Iacono, J.: Packing identical simple polygons is NP-hard. CoRR abs\/1209.5307 (2012)"},{"issue":"1","key":"36_CR5","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1287\/moor.1050.0168","volume":"31","author":"N Bansal","year":"2006","unstructured":"Bansal, N., Correa, J.R., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions: inapproximability results and approximation schemes. Math. Oper. Res. 31(1), 31\u201349 (2006)","journal-title":"Math. Oper. Res."},{"issue":"26\u201328","key":"36_CR6","doi-asserted-by":"publisher","first-page":"2572","DOI":"10.1016\/j.tcs.2010.03.019","volume":"411","author":"J Boyar","year":"2010","unstructured":"Boyar, J., Epstein, L., Levin, A.: Tight results for Next Fit and Worst Fit with resource augmentation. Theor. Comput. Sci. 411(26\u201328), 2572\u20132580 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"36_CR7","unstructured":"Chou, A.: NP-hard triangle packing problems. manuscript (2016)"},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"HI Christensen","year":"2017","unstructured":"Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63\u201379 (2017)","journal-title":"Comput. Sci. Rev."},{"key":"36_CR9","unstructured":"Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: A survey. In: Hochbaum, D. (ed.) Approximation algorithms for NP-hard Problems. PWS Publishing Co. (1997)"},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"Coffman Jr., E.G., Csirik, J., Galambos, G., Martello, S., Vigo, D.: Bin packing approximation algorithms: survey and classification. In: Pardalos, P.M., Du, D.Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, pp. 455\u2013531. Springer, New York (2013)","DOI":"10.1007\/978-1-4419-7997-1_35"},{"key":"36_CR11","unstructured":"Demaine, E.D., Fekete, S.P., Lang, R.J.: Circle packing for origami design is hard. CoRR abs\/1008.1224 (2010)"},{"issue":"31\u201333","key":"36_CR12","doi-asserted-by":"publisher","first-page":"2899","DOI":"10.1016\/j.tcs.2010.04.021","volume":"411","author":"L Epstein","year":"2010","unstructured":"Epstein, L.: Two-dimensional online bin packing with rotation. Theor. Comput. Sci. 411(31\u201333), 2899\u20132911 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"36_CR13","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s00224-007-9007-8","volume":"42","author":"L Epstein","year":"2008","unstructured":"Epstein, L., Ganot, A.: Optimal on-line algorithms to minimize makespan on two machines with resource augmentation. Theory Comput. Syst. 42(4), 431\u2013449 (2008)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"36_CR14","doi-asserted-by":"publisher","first-page":"1310","DOI":"10.1137\/11082782X","volume":"23","author":"L Epstein","year":"2013","unstructured":"Epstein, L., Levin, A.: Robust approximation schemes for cube packing. SIAM J. Optim. 23(2), 1310\u20131343 (2013)","journal-title":"SIAM J. Optim."},{"issue":"3\u20134","key":"36_CR15","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.disopt.2007.09.004","volume":"4","author":"L Epstein","year":"2007","unstructured":"Epstein, L., van Stee, R.: Online bin packing with resource augmentation. Discret. Optim. 4(3\u20134), 322\u2013333 (2007)","journal-title":"Discret. Optim."},{"key":"36_CR16","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0097-3165(75)90099-0","volume":"19","author":"P Erd\u0151s","year":"1975","unstructured":"Erd\u0151s, P., Graham, R.L.: On packing squares with equal squares. J. Combin. Theory Ser. A 19, 119\u2013123 (1975)","journal-title":"J. Combin. Theory Ser. A"},{"key":"36_CR17","unstructured":"Erickson, J., van der Hoog, I., Miltzow, T.: A framework for robust realistic geometric computations. CoRR abs\/1912.02278 (2019)"},{"key":"36_CR18","doi-asserted-by":"publisher","unstructured":"Fleischer, R., Wahl, M.: Online scheduling revisited. In: Paterson, M.S. (ed.) ESA 2000. LNCS, vol. 1879, pp. 202\u2013210. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-45253-2_19","DOI":"10.1007\/3-540-45253-2_19"},{"key":"36_CR19","doi-asserted-by":"crossref","unstructured":"Friedman, E.: Packing unit squares in squares: a survey and new results. Elec. J. Comb. 1000, DS7-Aug (2009)","DOI":"10.37236\/28"},{"key":"36_CR20","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-7091-2748-3_8","volume-title":"Analysis and Design of Algorithms in Combinatorial Optimization","author":"MR Garey","year":"1981","unstructured":"Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing problems - a survey. In: Ausiello, G., Lucertini, M. (eds.) Analysis and Design of Algorithms in Combinatorial Optimization, pp. 147\u2013172. Springer, New York (1981)"},{"issue":"1","key":"36_CR21","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s00454-004-1129-z","volume":"34","author":"T Gensane","year":"2005","unstructured":"Gensane, T., Ryckelynck, P.: Improved dense packings of congruent squares in a square. Discret. Comput. Geom. 34(1), 97\u2013109 (2005)","journal-title":"Discret. Comput. Geom."},{"key":"36_CR22","first-page":"179","volume":"106","author":"F G\u00f6bel","year":"1979","unstructured":"G\u00f6bel, F.: Geometrical packing and covering problems. Math Centrum Tracts 106, 179\u2013199 (1979)","journal-title":"Math Centrum Tracts"},{"key":"36_CR23","doi-asserted-by":"crossref","unstructured":"Hoberg, R., Rothvoss, T.: A logarithmic additive integrality gap for bin packing. In: Proceedings the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2616\u20132625. SIAM (2017)","DOI":"10.1137\/1.9781611974782.172"},{"issue":"4","key":"36_CR24","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"EG Coffman Jr","year":"1980","unstructured":"Coffman Jr., E.G., Garey, M.R., Johnson, D.S., Tarjan, R.E.: Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput. 9(4), 808\u2013826 (1980)","journal-title":"SIAM J. Comput."},{"key":"36_CR25","unstructured":"Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)"},{"issue":"6","key":"36_CR26","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1007\/s10951-017-0541-1","volume":"20","author":"DR Kowalski","year":"2017","unstructured":"Kowalski, D.R., Wong, P.W.H., Zavou, E.: Fault tolerant scheduling of tasks of two sizes under resource augmentation. J. Sched. 20(6), 695\u2013711 (2017). https:\/\/doi.org\/10.1007\/s10951-017-0541-1","journal-title":"J. Sched."},{"issue":"3","key":"36_CR27","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0743-7315(90)90019-L","volume":"10","author":"JY Leung","year":"1990","unstructured":"Leung, J.Y., Tam, T.W., Wong, C.S., Young, G.H., Chin, F.Y.L.: Packing squares into a square. J. Parallel Distrib. Comput. 10(3), 271\u2013275 (1990)","journal-title":"J. Parallel Distrib. Comput."},{"key":"36_CR28","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D Sleator","year":"1985","unstructured":"Sleator, D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28, 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"key":"36_CR29","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32, 652\u2013686 (1985)","journal-title":"J. ACM"},{"issue":"3","key":"36_CR30","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"key":"36_CR31","doi-asserted-by":"crossref","unstructured":"Stromquist, W.: Packing 10 or 11 unit squares in a square. Elec. J. Comb. 10, R8 (2003)","DOI":"10.37236\/1701"},{"issue":"4","key":"36_CR32","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"WF de la Vega","year":"1981","unstructured":"de la Vega, W.F., Lueker, G.S.: Bin packing can be solved within 1+$$\\epsilon $$ in linear time. Combinatorica 1(4), 349\u2013355 (1981)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-64843-5_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,16]],"date-time":"2021-04-16T15:52:31Z","timestamp":1618588351000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-64843-5_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030648428","9783030648435"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-64843-5_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"4 December 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dallas, TX","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 December 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 December 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/COCOA2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Springer OCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"104","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"55","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"53% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the Corona pandemic this event was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}