Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes

References

• Baker B. S., Brown D. J., Kasteff H. P. A 5/4 algorithm for two-dimensional packing. J. Algorithms (1981) 2:348–368Crossref, Google Scholar
• Berman P., Karpinski M. Improved approximation lower bounds on small occurrence optimization. (2003) Google Scholar
• Caprara A. Packing two-dimensional bins in harmony. Proc. 43rd IEEE Sympos. Foundations Comput. Sci. (FOCS) (2002) Vancouver, Canada(IEEE)490–499Google Scholar
• Caprara A., Lodi A., Monaci M. Fast approximation schemes for two-stage, two-dimensional bin packing. Math. Oper. Res. (2005) 30:136–156Link, Google Scholar
• Chekuri C., Khanna S. On multi-dimensional packing problems. Proc. 10th ACM-SIAM Sympos. Discrete Algorithms (SODA) (1999) Baltimore, MD(ACM-SIAM)185–194Google Scholar
• Chung F. R. K., Garey M. R., Johnson D. S. On packing two-dimensional bins. SIAM J. Algebraic Discrete Methods (1982) 3:66–76Crossref, Google Scholar
• Coffman E. G., Garey M. R., Johnson D. S., Hochbaum D. Approximation algorithms for bin packing: A survey. Approximation Algorithms for NP-Hard Problems (1996) (PWS Publishing, Boston, MA) 46–93Google Scholar
• Coffman E. G., Garey M. R., Johnson D. S., Tarjan R. E. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput. (1980) 9:808–826Crossref, Google Scholar
• Csirik J., van Vliet A. An on-line algorithm for multidimensional bin packing. Oper. Res. Lett. (1993) 13:149–158Crossref, Google Scholar
• Csirik J., Woeginger G., Fiat A., Woeginger G. On-line packing and covering problems. Online Algorithms: The State of the Art, Lecture Notes in Computer Science (1998) Vol. 1442(Springer)147–177Google Scholar
• Epstein L., van Stee R. Optimal online bounded space multidimensional packing. Proc. 15th ACM-SIAM Sympos. Discrete Algorithms (SODA) (2004) New Orleans, LA(ACM-SIAM)207–216Google Scholar
• Fernandez de la Vega W., Lueker G. Bin packing can be solved within 1 + ε in linear time. Combinatorica (1981) 1:349–355Crossref, Google Scholar
• Ferreira C. E., Miyazawa F. K., Wakabayashi Y. Packing squares into squares. Pesquisa Operacional (1999) 19:223–237Google Scholar
• Hazan E., Safra S., Schwartz O. On the complexity of approximating k-dimensional matching. Proc. 6th Internat. Workshop on Approximation Algorithms for Combin. Optim. Problems and of the 7th Internat. Workshop on Randomization and Comput. (RANDOM-APPROX), Lecture Notes in Computer Science (2003) Vol. 2764(Springer, Berlin, Germany) 83–97Google Scholar
• Jansen K., Zhang G. On rectangle packing: Maximizing benefits. Proc. 15th ACM-SIAM Sympos. Discrete Algorithms (SODA) (2004) (ACM-SIAM, New Orleans, LA) 197–206Google Scholar
• Kann V. Maximum bounded 3-dimensional matching is MAX SNP-complete. Inform. Processing Lett. (1991) 37:27–35Crossref, Google Scholar
• Karmarkar N., Karp R. M. An efficient approximation scheme for the one-dimensional bin-packing problem. Proc. 23rd IEEE Sympos. Foundations Comput. Sci. (FOCS) (1982) (IEEE, New York) 312–320Google Scholar
• Kenyon C., Rémila E. A near-optimal solution to a two-dimensional cutting stock problem. Math. Oper. Res. (2000) 25:645–656Link, Google Scholar
• Kleitman D. J., Krieger M. An optimal bound for two-dimensional packing. Proc. 16th IEEE Sympos. Foundations Comput. Sci. (FOCS) (1975) (IEEE, Berkeley, CA) 163–168Google Scholar
• Kohayakawa Y., Miyazawa F. K., Raghavan P., Wakabayashi Y. Multidimensional cube packing. Algorithmica (2004) 40:173–187Crossref, Google Scholar
• Korf R. Optimal rectangle packing: Initial results. Proc. 13th Internat. Conf. on Automated Planning and Scheduling (ICAPS) (2003) (AAAI, Trento, Italy) 287–295Google Scholar
• Lenstra H. W. Integer programming with a fixed number of variables. Math. Oper. Res. (1983) 8:538–548Link, Google Scholar
• Leung J. Y. T., Tam T. W., Wong C. S., Young G. H., Chin F. Y. L. Packing squares into a square. J. Parallel Distributed Comput. (1990) 10:271–275Crossref, Google Scholar
• Meir A., Moser L. On packing of squares and cubes. J. Combin. Theory. Ser. A (1968) 5:126–134Crossref, Google Scholar
• Moser L. Poorly formulated unsolved problems of combinatorial geometry. (1965) . MimeographedGoogle Scholar
• Murata H., Fujiyoshi K., Nakatake S., Kajitani Y. VLSI module placement based on rectangle-packing by the sequence-pair. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (1996) 15:1518–1524Crossref, Google Scholar
• Novotny P. On packing of squares into a rectangle. Archivum Mathematicum (1996) 32:75–83Google Scholar
• Petrank E. The hardness of approximation: Gap location. Comput. Complexity (1994) 4:133–157Crossref, Google Scholar
• Seiden S., van Stee R. New bounds for multi-dimensional packing. Algorithmica (2003) 36:261–293Crossref, Google Scholar
• Sevastianov S., Woeginger G. Makespan minimization in open shops: A polynomial time approximation scheme. Math. Programming Ser. B (1998) 82:191–198Google Scholar
• van Stee R. An approximation algorithm for square packing. Oper. Res. Lett. (2004) 32:535–539Crossref, Google Scholar
• Vazirani V.Approximation Algorithms (2001) (Springer, Berlin, Germany) Google Scholar
• Woeginger G. There is no asymptotic PTAS for two-dimensional vector packing. Inform. Processing Lett. (1997) 64:293–297Crossref, Google Scholar