{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,26]],"date-time":"2025-01-26T05:27:03Z","timestamp":1737869223957,"version":"3.33.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,1,4]],"date-time":"2008-01-04T00:00:00Z","timestamp":1199404800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2008,5]]},"DOI":"10.1007\/s00236-007-0067-7","type":"journal-article","created":{"date-parts":[[2008,1,3]],"date-time":"2008-01-03T12:48:48Z","timestamp":1199364528000},"page":"155-175","source":"Crossref","is-referenced-by-count":11,"title":["Two-dimensional packing with conflicts"],"prefix":"10.1007","volume":"45","author":[{"given":"Leah","family":"Epstein","sequence":"first","affiliation":[]},{"given":"Asaf","family":"Levin","sequence":"additional","affiliation":[]},{"given":"Rob","family":"van Stee","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,1,4]]},"reference":[{"issue":"1","key":"67_CR1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1287\/moor.1050.0168","volume":"31","author":"N. Bansal","year":"2006","unstructured":"Bansal, N., Correa, J., 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."},{"key":"67_CR2","unstructured":"Bansal, N., Sviridenko, M.: New approximability and inapproximability results for 2-dimensional packing. In: Proceedings of the 15th Annual Symposium on Discrete Algorithms, pp. 189\u2013196. ACM\/SIAM, New York\/Philadelphia (2004)"},{"key":"67_CR3","doi-asserted-by":"crossref","unstructured":"Caprara, A.: Packing 2-dimensional bins in harmony. In: Proceedings of 43rd Annual Symposium on Foundations of Computer Science, pp. 490\u2013499 (2002)","DOI":"10.1109\/SFCS.2002.1181973"},{"key":"67_CR4","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1137\/0603007","volume":"3","author":"F.R.K. Chung","year":"1982","unstructured":"Chung, F.R.K., Garey, M.R., Johnson, D.S.: On packing two-dimensional bins. SIAM J. Algebraic Discrete Methods 3, 66\u201376 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"67_CR5","volume-title":"Approximation algorithms","author":"E.G. Coffman","year":"1997","unstructured":"Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D. (eds) Approximation algorithms, PWS Publishing Company, Boston (1997)"},{"key":"67_CR6","unstructured":"Correa, J., Kenyon, C.: Approximation schemes for multidimensional packing. In: Proceedings of the 15th ACM\/SIAM Symposium on Discrete Algorithms, pp. 179\u2013188. ACM\/SIAM, New York\/Philadelphia (2004)"},{"key":"67_CR7","doi-asserted-by":"crossref","unstructured":"Csirik, J., Woeginger, G.J.: On-line packing and covering problems. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms: The State of the Art, pp. 147\u2013177 (1998)","DOI":"10.1007\/BFb0029568"},{"key":"67_CR8","doi-asserted-by":"crossref","unstructured":"Epstein, L., Levin, A.: On bin packing with conflicts. In: Proceedings of the 4th Workshop on Approximation and online Algorithms (WAOA2006), pp. 160\u2013173 (2006)","DOI":"10.1007\/11970125_13"},{"key":"67_CR9","unstructured":"Epstein, L., van Stee, R.: Optimal online bounded space multidimensional packing. In: Proceedings of of 15th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201904), pp. 207\u2013216 (2004)"},{"key":"67_CR10","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Company, New York (1979)"},{"key":"67_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M. Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization. Springer, Heidelberg (1993)"},{"issue":"2","key":"67_CR12","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E. Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23(2), 317\u2013327 (1976)","journal-title":"J. ACM"},{"key":"67_CR13","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1017\/S0963548300001826","volume":"5","author":"M. Hujter","year":"1996","unstructured":"Hujter, M., Tuza, Z.: Precoloring extension, III: Classes of perfect graphs. Comb. Probab. Comput. 5, 35\u201356 (1996)","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"67_CR14","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C.A.J. Hurkens","year":"1989","unstructured":"Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. 2(1), 68\u201372 (1989)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"67_CR15","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1023\/A:1009871302966","volume":"3","author":"K. Jansen","year":"1999","unstructured":"Jansen, K.: An approximation scheme for bin packing with conflicts. J. Comb. Optim. 3(4), 363\u2013377 (1999)","journal-title":"J. Comb. Optim."},{"key":"67_CR16","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1006\/inco.1996.2616","volume":"132","author":"K. Jansen","year":"1997","unstructured":"Jansen, K., \u00d6hring, S.: Approximation algorithms for time constrained scheduling. Inf. Comp. 132, 85\u2013108 (1997)","journal-title":"Inf. Comp."},{"issue":"4","key":"67_CR17","doi-asserted-by":"crossref","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)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"67_CR18","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s00453-004-1102-5","volume":"40","author":"Y. Kohayakawa","year":"2004","unstructured":"Kohayakawa, Y., Miyazawa, F.K.: Prabhakar Raghavan, and Yoshiko Wakabayashi. Multidimensional cube packing. Algorithmica 40(3), 173\u2013187 (2004)","journal-title":"Algorithmica"},{"issue":"3","key":"67_CR19","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"C.C. Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A simple online bin packing algorithm. J. ACM 32(3), 562\u2013572 (1985)","journal-title":"J. ACM"},{"key":"67_CR20","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0743-7315(90)90019-L","volume":"10","author":"J.Y.-T. Leung","year":"1990","unstructured":"Leung, J.Y.-T., Tam, T.W., Wong, C.S., Young, G.H., Chin, F.Y.L.: Packing squares into a square. J. Parallel Distrib. Comput. 10, 271\u2013275 (1990)","journal-title":"J. Parallel Distrib. Comput."},{"key":"67_CR21","unstructured":"Marx, D.: Precoloring extension. http:\/\/www.cs.bme.hu\/dmarx\/prext.html"},{"key":"67_CR22","doi-asserted-by":"crossref","unstructured":"Marx, D.: Precoloring extension on chordal graphs. In: Graph Theory in Paris. Proceedings of a Conference in Memory of Claude Berge, Trends in Mathematics, pp. 255\u2013270. Birkh\u00e4user, Basel (2007)","DOI":"10.1007\/978-3-7643-7400-6_20"},{"key":"67_CR23","unstructured":"McCloskey, B., Shankar, A.: Approaches to bin packing with clique-graph conflicts. Technical Report UCB\/CSD-05-1378, EECS Department, University of California, Berkeley (2005)"},{"key":"67_CR24","doi-asserted-by":"crossref","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 Ser. A 5, 126\u2013134 (1968)","journal-title":"J. Comb. Theory Ser. A"},{"key":"67_CR25","unstructured":"Oh, Y., Son, S.H.: On a constrained bin-packing problem. Technical Report CS-95-14, Department of Computer Science, University of Virginia (1995)"},{"key":"67_CR26","unstructured":"Schrijver, A.: Combinatorial optimization polyhedra and efficiency. Springer, Heidelberg (2003)"},{"issue":"3","key":"67_CR27","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/s00453-003-1016-7","volume":"36","author":"S.S. Seiden","year":"2003","unstructured":"Seiden, S.S., van Stee, R.: New bounds for multi-dimensional packing. Algorithmica 36(3), 261\u2013293 (2003)","journal-title":"Algorithmica"},{"key":"67_CR28","unstructured":"Ullman, J.D.: The performance of a memory allocation algorithm. Technical Report 100, Princeton University, Princeton (1971)"},{"issue":"6","key":"67_CR29","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1016\/j.orl.2004.02.003","volume":"32","author":"R. Stee van","year":"2004","unstructured":"van Stee, R.: An approximation algorithm for square packing. Oper. Res. Lett. 32(6), 535\u2013539 (2004)","journal-title":"Oper. Res. Lett."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-007-0067-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-007-0067-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-007-0067-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,25]],"date-time":"2025-01-25T07:48:39Z","timestamp":1737791319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-007-0067-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,4]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["67"],"URL":"https:\/\/doi.org\/10.1007\/s00236-007-0067-7","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2008,1,4]]}}}