Top

Journal of Combinatorial Optimization

Published in:

01-01-2015

Packing cubes into a cube is NP-complete in the strong sense

Authors: Yiping Lu, Danny Z. Chen, Jianzhong Cha

Published in: Journal of Combinatorial Optimization | Issue 1/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

While the problem of packing two-dimensional squares into a square, in which a set of squares is packed into a big square, has been proved to be NP-complete, the computational complexity of the d-dimensional (\( d\ge 3 \)) problems of packing hypercubes into a hypercube remains an open question (Acta Inf 41(9):595–606, 2005; Theor Comput Sci 410(44):4504–4532, 2009). In this paper, the authors show that the three-dimensional problem version of packing cubes into a cube is NP-complete in the strong sense.

previous article New bounds for the balloon popping problem

next article Complexity analysis and algorithms for the Program Download Problem

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

A cubic space or box has 6 faces, as shown in Fig. 4b, a. In such a figure, we call its visible faces that are parallel to the \(x\times y\) plane, \(y\times z\) plane, or \(z\times x\) plane the front face, the top face, or the left face, respectively, and call its invisible faces that are parallel to the \(x \times y\) plane, \(y \times z\) plane, or \(z\times x\) plane the back face, the bottom face, or the right face, respectively.

Region \(\varepsilon -\varepsilon '\) is the region \(\varepsilon \) minus the region \(\varepsilon '\), similar is the meaning of region \(\zeta -\zeta '\). See Fig. 3b for region \(\varepsilon \) and region \(\zeta \).

Bansal N, Correa JR, Kenyon C, Sviridenko M (2006) Bin packing in multiple dimensions: Inapproximability results and approximation schemes. Math Oper Res 31(1):31–49CrossRefMATHMathSciNet

Caprara A, Lodi A, Monaci M (2005) Fast approximation schemes for two-stage, two-dimensional bin packing. Math Oper Res 30:136–156CrossRefMathSciNet

Chung FRK, Garey MR, Johnson DS (1982) On packing two-dimensional bins. SIAM J Algebraic Discret Methods 3:66–76CrossRefMATHMathSciNet

Correa JR, Kenyon C (2004) Approximation schemes for multidimensional packing. In: Proceedings of 15th ACM-SIAM symposium on discrete algorithms 179–188

Epstein L, van Stee R (2005) Online square and cube packing. Acta Inf 41(9):595–606CrossRefMATH

Garey M, Johnson D (1979) Computer and intractability—a guide to the theory of np-completeness. Freeman, New York

Harren R (2009) Approximation algorithms for orthogonal packing problems for hypercubes. Theor Comput Sci 410(44):4504–4532CrossRefMATHMathSciNet

Kohayakawa Y, Miyazawa FK, Raghavan P, Wakabayashi Y (2004) Multidimensional cube packing. Algorithmica 40:173–187CrossRefMATHMathSciNet

Leung JYT, Tam WT, Wong CS, Chin FYL (1990) Packing squares into a square. J Parallel Distrib Comput 10:271–275CrossRefMathSciNet

Li K, Cheng KH (1989) Complexity of resource allocation and job scheduling problems in partitionable mesh connected systems. Proceedings of 1st annual IEEE symposium of parallel and distributed processing, Silver Spring, MD pp 358–365

Miyazawa F, Wakabayashi Y (2003) Cube packing. Theor Comput Sci 297:355–366CrossRefMATHMathSciNet

Waescher G, Haussner H, Schumann H (2007) An improved typology of cutting and packing problems. Euro J Oper Res 183(3):1109–1130CrossRefMATH

Title: Packing cubes into a cube is NP-complete in the strong sense
Authors: Yiping Lu
Danny Z. Chen
Jianzhong Cha
Publication date: 01-01-2015
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2015
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-013-9701-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2015

Complexity analysis and algorithms for the Program Download Problem

Online unbounded batch scheduling on parallel machines with delivery times

Improved lower bounds for the online bin packing problem with cardinality constraints

Parametric power supply networks

An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs

DVS scheduling in a line or a star network of processors

Premium Partner