{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T21:40:23Z","timestamp":1737322823738,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_3","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T11:36:39Z","timestamp":1185104199000},"page":"34-45","source":"Crossref","is-referenced-by-count":1,"title":["Approximation Algorithms for 3D Orthogonal Knapsack"],"prefix":"10.1007","author":[{"given":"Florian","family":"Diedrich","sequence":"first","affiliation":[]},{"given":"Rolf","family":"Harren","sequence":"additional","affiliation":[]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[]},{"given":"Ralf","family":"Th\u00f6le","sequence":"additional","affiliation":[]},{"given":"Henning","family":"Thomas","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"3_CR1","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/0196-6774(81)90034-1","volume":"2","author":"B.S. Baker","year":"1981","unstructured":"Baker, B.S., Brown, D.J., Katseff, H.P.: A 5\/4 algorithm for two-dimensional packing. Journal of Algorithms\u00a02(4), 348\u2013368 (1981)","journal-title":"Journal of Algorithms"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1287\/moor.1050.0168","volume":"31","author":"N. Bansal","year":"2006","unstructured":"Bansal, N., et al.: Bin packing in multiple dimensions: inapproximability results and approximation schemes. Mathematics of Operations Research\u00a031, 31\u201349 (2006)","journal-title":"Mathematics of Operations Research"},{"key":"3_CR3","unstructured":"Bansal, N., et al.: Harmonic algorithm for 3-dimensional strip packing problem. Accepted at the ACM-SIAM Symposium on Discrete Algorithms (SODA) (2007)"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Caprara, A.: Packing two-dimensional bins in harmony. In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 490\u2013499 (2005)","DOI":"10.1109\/SFCS.2002.1181973"},{"key":"3_CR5","unstructured":"Diedrich, F.: Approximative Algorithmen f\u00fcr Rucksackprobleme. Diploma thesis, Institut f\u00fcr Informatik und Praktische Mathematik der Christian-Albrechts-Universit\u00e4t zu Kiel (2004)"},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(94)90152-X","volume":"130","author":"A. Feldmann","year":"1994","unstructured":"Feldmann, A., Sgall, J., Teng, S.-H.: Dynamic scheduling on parallel machines. Theoretical Computer Science (Special Issue on Dynamic and On-line Algorithms)\u00a0130(1), 49\u201372 (1994)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"3_CR7","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega, W., Lueker, G.: Bin packing can be solved within 1\u2009+\u2009\u03b5 in linear time. Combinatorica\u00a01(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/11786986_22","volume-title":"Automata, Languages and Programming","author":"R. Harren","year":"2006","unstructured":"Harren, R.: Approximating the Orthogonal Knapsack Problem for Hypercubes. In: Bugliesi, M., et al. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 238\u2013249. Springer, Heidelberg (2006)"},{"key":"3_CR9","unstructured":"Harren, R.: Approximation Mehrdimensionaler Packungsprobleme. Diploma thesis, Universit\u00e4t Dortmund (2006)"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Jansen, K., Solis-Oba, R.: An asymptotic approximation algorithm for 3d-strip packing. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 143\u2013152 (2006)","DOI":"10.1145\/1109557.1109575"},{"key":"3_CR11","unstructured":"Jansen, K., Zhang, G.: Maximizing the total profit of rectangles packed into a rectangle. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 197\u2013206 (2004)"},{"key":"3_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H. Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004)"},{"key":"3_CR13","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. Mathematics of Operations Research\u00a025, 645\u2013656 (2000)","journal-title":"Mathematics of Operations Research"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"E. Lawler","year":"1979","unstructured":"Lawler, E.: Fast approximation algorithms for knapsack problems. Mathematics of Operations Research\u00a04, 339\u2013356 (1979)","journal-title":"Mathematics of Operations Research"},{"key":"3_CR15","doi-asserted-by":"publisher","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., et al.: Packing squares into a square. Journal of Parallel and Distributed Computing\u00a010, 271\u2013275 (1990)","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"5","key":"3_CR16","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1137\/0219059","volume":"19","author":"K. Li","year":"1990","unstructured":"Li, K., Cheng, K.-H.: On three-dimensional packing. SIAM Journal of Computation\u00a019(5), 847\u2013867 (1990), doi:10.1137\/0219059","journal-title":"SIAM Journal of Computation"},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1016\/0196-6774(92)90058-K","volume":"13","author":"K. Li","year":"1992","unstructured":"Li, K., Cheng, K.-H.: Heuristic algorithms for on-line packing in three dimensions. Journal of Algorithms\u00a013, 589\u2013605 (1992)","journal-title":"Journal of Algorithms"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"1262","DOI":"10.1007\/BF02882475","volume":"42","author":"R.H. Li","year":"1997","unstructured":"Li, R.H., Yue, M.Y.: The proof of $\\text{FFD}(\\text{L}) \\leq (11\/9)\\text{OPT}(\\text{L})+(7\/9)$ . Chinese Science Bulletin\u00a042, 1262\u20131265 (1997)","journal-title":"Chinese Science Bulletin"},{"key":"3_CR19","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"S. Martello","year":"1990","unstructured":"Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester (1990)"},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/BF02523692","volume":"18","author":"F.K. Miyazawa","year":"1997","unstructured":"Miyazawa, F.K., Wakabayashi, Y.: An algorithm for the three-dimensional packing problem with asymptotic performance analysis. Algorithmica\u00a018, 122\u2013144 (1997)","journal-title":"Algorithmica"},{"key":"3_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/BFb0049416","volume-title":"Algorithms - ESA \u201994","author":"I. Schiermeyer","year":"1994","unstructured":"Schiermeyer, I.: Reverse-fit: A 2-optimal algorithm for packing rectangles. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.\u00a0855, pp. 290\u2013299. Springer, Heidelberg (1994)"},{"issue":"1","key":"3_CR22","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(80)90121-0","volume":"10","author":"D.D.K. Sleator","year":"1980","unstructured":"Sleator, D.D.K.: A 2.5 times optimal algorithm for packing in two dimensions. Information Processing Letters\u00a010(1), 37\u201340 (1980)","journal-title":"Information Processing Letters"},{"issue":"2","key":"3_CR23","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 Journal of Computation\u00a026(2), 401\u2013409 (1997)","journal-title":"SIAM Journal of Computation"},{"key":"3_CR24","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"key":"3_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/b14019","volume-title":"Algorithms and Computation","author":"G. Zhang","year":"2003","unstructured":"Zhang, G., Ye, D.: Online Scheduling of Parallel Jobs with Dependencies on 2-Dimensional Meshes. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 329\u2013338. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T21:27:05Z","timestamp":1737322025000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_3","relation":{},"subject":[]}}