Abstract
We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is forbidden; we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms with approximation ratios 9 + ε and 8 + ε as well as an algorithm with approximation ratio 7 + ε that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Topics: Algorithms, computational and structural complexity.
Research supported in part by DFG Project, “Entwicklung und Analyse von Approximativen Algorithmen für Gemischte und Verallgemeinerte Packungs- und Überdeckungsprobleme, JA 612/10-1”, in part by the German Academic Exchange Service DAAD, in part by project AEOLUS, EU contract number 015964, and in part by a grant “DAAD Doktorandenstipendium” of the German Academic Exchange Service DAAD. Part of this work was done while visiting the ID-IMAG, ENSIMAG, Grenoble.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baker, B.S., Brown, D.J., Katseff, H.P.: A 5/4 algorithm for two-dimensional packing. Journal of Algorithms 2(4), 348–368 (1981)
Bansal, N., et al.: Bin packing in multiple dimensions: inapproximability results and approximation schemes. Mathematics of Operations Research 31, 31–49 (2006)
Bansal, N., et al.: Harmonic algorithm for 3-dimensional strip packing problem. Accepted at the ACM-SIAM Symposium on Discrete Algorithms (SODA) (2007)
Caprara, A.: Packing two-dimensional bins in harmony. In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 490–499 (2005)
Diedrich, F.: Approximative Algorithmen für Rucksackprobleme. Diploma thesis, Institut für Informatik und Praktische Mathematik der Christian-Albrechts-Universität zu Kiel (2004)
Feldmann, A., Sgall, J., Teng, S.-H.: Dynamic scheduling on parallel machines. Theoretical Computer Science (Special Issue on Dynamic and On-line Algorithms) 130(1), 49–72 (1994)
Fernandez de la Vega, W., Lueker, G.: Bin packing can be solved within 1 + ε in linear time. Combinatorica 1(4), 349–355 (1981)
Harren, R.: Approximating the Orthogonal Knapsack Problem for Hypercubes. In: Bugliesi, M., et al. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 238–249. Springer, Heidelberg (2006)
Harren, R.: Approximation Mehrdimensionaler Packungsprobleme. Diploma thesis, Universität Dortmund (2006)
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–152 (2006)
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–206 (2004)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004)
Kenyon, C., Rémila, E.: A near-optimal solution to a two dimensional cutting stock problem. Mathematics of Operations Research 25, 645–656 (2000)
Lawler, E.: Fast approximation algorithms for knapsack problems. Mathematics of Operations Research 4, 339–356 (1979)
Leung, J.Y.-T., et al.: Packing squares into a square. Journal of Parallel and Distributed Computing 10, 271–275 (1990)
Li, K., Cheng, K.-H.: On three-dimensional packing. SIAM Journal of Computation 19(5), 847–867 (1990), doi:10.1137/0219059
Li, K., Cheng, K.-H.: Heuristic algorithms for on-line packing in three dimensions. Journal of Algorithms 13, 589–605 (1992)
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 42, 1262–1265 (1997)
Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester (1990)
Miyazawa, F.K., Wakabayashi, Y.: An algorithm for the three-dimensional packing problem with asymptotic performance analysis. Algorithmica 18, 122–144 (1997)
Schiermeyer, I.: Reverse-fit: A 2-optimal algorithm for packing rectangles. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 290–299. Springer, Heidelberg (1994)
Sleator, D.D.K.: A 2.5 times optimal algorithm for packing in two dimensions. Information Processing Letters 10(1), 37–40 (1980)
Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM Journal of Computation 26(2), 401–409 (1997)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)
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. 2906, pp. 329–338. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Diedrich, F., Harren, R., Jansen, K., Thöle, R., Thomas, H. (2007). Approximation Algorithms for 3D Orthogonal Knapsack. In: Cai, JY., Cooper, S.B., Zhu, H. (eds) Theory and Applications of Models of Computation. TAMC 2007. Lecture Notes in Computer Science, vol 4484. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72504-6_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-72504-6_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72503-9
Online ISBN: 978-3-540-72504-6
eBook Packages: Computer ScienceComputer Science (R0)