{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:43Z","timestamp":1759638763075,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,8,21]],"date-time":"2015-08-21T00:00:00Z","timestamp":1440115200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["306860\/2010-4"],"award-info":[{"award-number":["306860\/2010-4"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["477692\/2012-5"],"award-info":[{"award-number":["477692\/2012-5"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001807","name":"FAPESP","doi-asserted-by":"crossref","award":["2013\/02434-8"],"award-info":[{"award-number":["2013\/02434-8"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001807","name":"FAPESP","doi-asserted-by":"crossref","award":["2010\/20710-4"],"award-info":[{"award-number":["2010\/20710-4"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001807","name":"FAPESP","doi-asserted-by":"crossref","award":["2013\/21744-8"],"award-info":[{"award-number":["2013\/21744-8"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["303987\/2010-3"],"award-info":[{"award-number":["303987\/2010-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["477203\/2012-4"],"award-info":[{"award-number":["477203\/2012-4"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001807","name":"FAPESP","doi-asserted-by":"crossref","award":["2013\/03447-6"],"award-info":[{"award-number":["2013\/03447-6"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MaClinC"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,10]]},"DOI":"10.1007\/s00453-015-0052-4","type":"journal-article","created":{"date-parts":[[2015,8,20]],"date-time":"2015-08-20T19:20:35Z","timestamp":1440098435000},"page":"536-568","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Polynomial-Time Approximation Schemes for Circle and Other Packing Problems"],"prefix":"10.1007","volume":"76","author":[{"given":"Fl\u00e1vio K.","family":"Miyazawa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lehilton L. C.","family":"Pedrosa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafael C. S.","family":"Schouery","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maxim","family":"Sviridenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshiko","family":"Wakabayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,21]]},"reference":[{"issue":"4","key":"52_CR1","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1137\/0209064","volume":"9","author":"B Baker","year":"1980","unstructured":"Baker, B., Coffman Jr, E., Rivest, R.: Orthogonal packings in two dimensions. SIAM J. Comput. 9(4), 846\u2013855 (1980). doi: 10.1137\/0209064","journal-title":"SIAM J. Comput."},{"issue":"4","key":"52_CR2","doi-asserted-by":"publisher","first-page":"1256","DOI":"10.1137\/080736831","volume":"39","author":"N Bansal","year":"2010","unstructured":"Bansal, N., Caprara, A., Sviridenko, M.: A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM J. Comput. 39(4), 1256\u20131278 (2010). doi: 10.1137\/080736831","journal-title":"SIAM J. Comput."},{"issue":"1","key":"52_CR3","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). doi: 10.1287\/moor.1050.0168","journal-title":"Math. Oper. Res."},{"issue":"2","key":"52_CR4","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1137\/070691607","volume":"42","author":"N Bansal","year":"2013","unstructured":"Bansal, N., Han, X., Iwama, K., Sviridenko, M., Zhang, G.: A harmonic algorithm for the 3D strip packing problem. SIAM J. Comput. 42(2), 579\u2013592 (2013). doi: 10.1137\/070691607","journal-title":"SIAM J. Comput."},{"key":"52_CR5","doi-asserted-by":"publisher","unstructured":"Bansal, N., Khan, A.: Improved approximation algorithm for two-dimensional bin packing. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, pp. 13\u201325 (2014). doi: 10.1137\/1.9781611973402.2","DOI":"10.1137\/1.9781611973402.2"},{"issue":"6","key":"52_CR6","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S Basu","year":"1996","unstructured":"Basu, S., Pollack, R., Roy, M.F.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43(6), 1002\u20131045 (1996). doi: 10.1145\/235809.235813","journal-title":"J. ACM"},{"key":"52_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry","author":"S Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.F.: Algorithms in Real Algebraic Geometry. Springer, Berlin (2006)"},{"issue":"7","key":"52_CR8","doi-asserted-by":"publisher","first-page":"1318","DOI":"10.1016\/j.cor.2009.09.017","volume":"37","author":"EG Birgin","year":"2010","unstructured":"Birgin, E.G., Gentil, J.M.: New and improved results for packing identical unitary radius circles within triangles, rectangles and strips. Comput. Oper. Res. 37(7), 1318\u20131327 (2010). doi: 10.1016\/j.cor.2009.09.017","journal-title":"Comput. Oper. Res."},{"key":"52_CR9","doi-asserted-by":"publisher","unstructured":"Caprara, A.: Packing 2-dimensional bins in harmony. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 490\u2013499 (2002). doi: 10.1109\/SFCS.2002.1181973","DOI":"10.1109\/SFCS.2002.1181973"},{"key":"52_CR10","doi-asserted-by":"publisher","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Inapproximability results for orthogonal rectangle packing problems with rotations. In: Calamoneri, T., Finocchi, I., Italiano, G. (eds.) Algorithms and Complexity, Lecture Notes in Computer Science, vol. 3998, pp. 199\u2013210. Springer, Berlin (2006). doi: 10.1007\/11758471_21","DOI":"10.1007\/11758471_21"},{"issue":"1","key":"52_CR11","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1137\/0603007","volume":"3","author":"F Chung","year":"1982","unstructured":"Chung, F., Garey, M., Johnson, D.: On packing two-dimensional bins. SIAM J. Algebraic Discrete Methods 3(1), 66\u201376 (1982). doi: 10.1137\/0603007","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"4","key":"52_CR12","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"E Coffman Jr","year":"1980","unstructured":"Coffman Jr, E., Garey, M., Johnson, D., Tarjan, R.: Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput. 9(4), 808\u2013826 (1980). doi: 10.1137\/0209062","journal-title":"SIAM J. Comput."},{"key":"52_CR13","doi-asserted-by":"publisher","unstructured":"Coffman, J.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","DOI":"10.1007\/978-1-4419-7997-1_35"},{"key":"52_CR14","doi-asserted-by":"publisher","unstructured":"Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decompostion. In: Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, pp. 134\u2013183 (1975). doi: 10.1007\/3-540-07407-4_17","DOI":"10.1007\/3-540-07407-4_17"},{"key":"52_CR15","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Fekete, S.P., Lang, R.J.: Circle packing for origami design is hard. In: Proceedings of the 5th International Conference on Origami in Science, pp. 609\u2013626 (2010)","DOI":"10.1201\/b10971-52"},{"key":"52_CR16","doi-asserted-by":"publisher","unstructured":"Eisenbrand, F.: Fast integer programming in fixed dimension. In: Di\u00a0Battista, G., Zwick, U. (eds.) Algorithms\u2014ESA 2003, Lecture Notes in Computer Science, vol. 2832, pp. 196\u2013207. Springer Berlin (2003). doi: 10.1007\/978-3-540-39658-1_20","DOI":"10.1007\/978-3-540-39658-1_20"},{"key":"52_CR17","doi-asserted-by":"publisher","unstructured":"Fernandez de La Vega, W., Lueker, G.S.: Bin packing can be solved within $$1 + \\varepsilon $$ 1 + \u03b5 in linear time. Combinatorica 1(4), 349\u2013355 (1981). doi: 10.1007\/BF02579456","DOI":"10.1007\/BF02579456"},{"issue":"3","key":"52_CR18","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/0377-2217(95)00032-L","volume":"84","author":"JA George","year":"1995","unstructured":"George, J.A., George, J.M., Lamar, B.W.: Packing different-sized circles into a rectangular container. Eur. J. Oper. Res. 84(3), 693\u2013712 (1995). doi: 10.1016\/0377-2217(95)00032-L","journal-title":"Eur. J. Oper. Res."},{"issue":"1\u20132","key":"52_CR19","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","volume":"5","author":"DY Grigor\u2019ev","year":"1988","unstructured":"Grigor\u2019ev, D.Y., Vorobjov Jr, N.N.: Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput. 5(1\u20132), 37\u201364 (1988). doi: 10.1016\/S0747-7171(88)80005-1","journal-title":"J. Symb. Comput."},{"key":"52_CR20","doi-asserted-by":"publisher","unstructured":"Harren, R., Jansen, K., Pr\u00e4del, L., van Stee, R.: A $$(5\/3+\\varepsilon )$$ ( 5 \/ 3 + \u03b5 ) -approximation for strip packing. In: Proceedings of the 12th Algorithms and Data Structures Symposium, pp. 475\u2013487 (2011). doi: 10.1007\/978-3-642-22300-6_40","DOI":"10.1007\/978-3-642-22300-6_40"},{"key":"52_CR21","doi-asserted-by":"publisher","unstructured":"Harren, R., van Stee, R.: Improved absolute approximation ratios for two-dimensional packing problems. In: Proceedings of the 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, pp. 177\u2013189 (2009). doi: 10.1007\/978-3-642-03685-9_14","DOI":"10.1007\/978-3-642-03685-9_14"},{"issue":"1","key":"52_CR22","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s10951-009-0110-3","volume":"15","author":"R Harren","year":"2012","unstructured":"Harren, R., van Stee, R.: Absolute approximation ratios for packing rectangles into bins. J. Sched. 15(1), 63\u201375 (2012). doi: 10.1007\/s10951-009-0110-3","journal-title":"J. Sched."},{"key":"52_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1155\/2009\/150624","volume":"2009","author":"M Hifi","year":"2009","unstructured":"Hifi, M., M\u2019Hallah, R.: A literature review on circle and sphere packing problems: models and methodologies. Adv. Oper. Res. 2009, 1\u201322 (2009). doi: 10.1155\/2009\/150624","journal-title":"Adv. Oper. Res."},{"key":"52_CR24","doi-asserted-by":"publisher","unstructured":"Jansen, K., Pr\u00e4del, L.: New approximability results for two-dimensional bin packing. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 919\u2013936 (2013). doi: 10.1137\/1.9781611973105.66","DOI":"10.1137\/1.9781611973105.66"},{"key":"52_CR25","doi-asserted-by":"publisher","unstructured":"Jansen, K., Pr\u00e4del, L.: A new asymptotic approximation algorithm for 3-dimensional strip packing. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A. (eds.) SOFSEM 2014: Theory and Practice of Computer Science, Lecture Notes in Computer Science, vol. 8327, pp. 327\u2013338. Springer International Publishing (2014). doi: 10.1007\/978-3-319-04298-5_29","DOI":"10.1007\/978-3-319-04298-5_29"},{"key":"52_CR26","doi-asserted-by":"publisher","unstructured":"Jansen, K., Pr\u00e4del, L.: New approximability results for two-dimensional bin packing. Algorithmica pp. 1\u201362 (2014). doi: 10.1007\/s00453-014-9943-z","DOI":"10.1007\/s00453-014-9943-z"},{"key":"52_CR27","doi-asserted-by":"crossref","unstructured":"Jansen, K., Solis-Oba, R.: An asymptotic approximation algorithm for 3d-strip packing. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 143\u2013152 (2006)","DOI":"10.1145\/1109557.1109575"},{"issue":"4","key":"52_CR28","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1287\/moor.25.4.645.12118","volume":"25","author":"C Kenyon","year":"2000","unstructured":"Kenyon, C., R\u00e9mila, E.: A near-optimal solution to a two-dimensional cutting stock problem. Math. Oper. Res. 25(4), 645\u2013656 (2000). doi: 10.1287\/moor.25.4.645.12118","journal-title":"Math. Oper. Res."},{"issue":"3","key":"52_CR29","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s00453-004-1102-5","volume":"40","author":"Y Kohayakawa","year":"2004","unstructured":"Kohayakawa, Y., Miyazawa, F., Raghavan, P., Wakabayashi, Y.: Multidimensional cube packing. Algorithmica 40(3), 173\u2013187 (2004). doi: 10.1007\/s00453-004-1102-5","journal-title":"Algorithmica"},{"issue":"4","key":"52_CR30","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Jr Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"issue":"5","key":"52_CR31","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1137\/0219059","volume":"19","author":"K Li","year":"1990","unstructured":"Li, K., Cheng, K.: On three-dimensional packing. SIAM J. Comput. 19(5), 847\u2013867 (1990). doi: 10.1137\/0219059","journal-title":"SIAM J. Comput."},{"issue":"2","key":"52_CR32","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/S0021-9800(68)80047-X","volume":"5","author":"A Meir","year":"1968","unstructured":"Meir, A., Moser, L.: On packing of squares and cubes. J. Comb. Theory 5(2), 126\u2013134 (1968). doi: 10.1016\/S0021-9800(68)80047-X","journal-title":"J. Comb. Theory"},{"issue":"1","key":"52_CR33","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/BF02523692","volume":"18","author":"F Miyazawa","year":"1997","unstructured":"Miyazawa, F., Wakabayashi, Y.: An algorithm for the three-dimensional packing problem with asymptotic performance analysis. Algorithmica 18(1), 122\u2013144 (1997). doi: 10.1007\/BF02523692","journal-title":"Algorithmica"},{"key":"52_CR34","doi-asserted-by":"publisher","unstructured":"Schiermeyer, I.: Reverse-fit: A 2-optimal algorithm for packing rectangles. In: Proceedings of the Second Annual European Symposium on Algorithms, pp. 290\u2013299 (1994). doi: 10.1007\/BFb0049416","DOI":"10.1007\/BFb0049416"},{"issue":"1","key":"52_CR35","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(80)90121-0","volume":"10","author":"DD Sleator","year":"1980","unstructured":"Sleator, D.D.: A 2.5 times optimal algorithm for packing in two dimensions. Inf. Process. Lett. 10(1), 37\u201340 (1980). doi: 10.1016\/0020-0190(80)90121-0","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"52_CR36","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S0097539793255801","volume":"26","author":"A Steinberg","year":"1997","unstructured":"Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput. 26(2), 401\u2013409 (1997). doi: 10.1137\/S0097539793255801","journal-title":"SIAM J. Comput."},{"key":"52_CR37","volume-title":"New Approaches to Circle Packing in a Square","author":"PG Szab\u00f3","year":"2007","unstructured":"Szab\u00f3, P.G., Mark\u00f3t, M.C., Csendes, T., Specht, E., Casado, L., Garc\u00eda, I.: New Approaches to Circle Packing in a Square. Springer, Berlin (2007)"},{"key":"52_CR38","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"A Tarski","year":"1951","unstructured":"Tarski, A.: A Decision Method for Elementary Algebra and Geometry. University of California Press, Berkeley (1951)"},{"issue":"3","key":"52_CR39","doi-asserted-by":"publisher","first-page":"1109","DOI":"10.1016\/j.ejor.2005.12.047","volume":"183","author":"G W\u00e4scher","year":"2007","unstructured":"W\u00e4scher, G., Hau\u00dfner, H., Schumann, H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183(3), 1109\u20131130 (2007). doi: 10.1016\/j.ejor.2005.12.047","journal-title":"Eur. J. Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0052-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0052-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0052-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,20]],"date-time":"2022-05-20T18:41:22Z","timestamp":1653072082000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0052-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,21]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,10]]}},"alternative-id":["52"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0052-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2015,8,21]]}}}