nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.01.2015

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

verfasst von: Yiping Lu, Danny Z. Chen, Jianzhong Cha

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel New bounds for the balloon popping problem

Nächster Artikel Complexity analysis and algorithms for the Program Download Problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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

Titel: Packing cubes into a cube is NP-complete in the strong sense
verfasst von: Yiping Lu
Danny Z. Chen
Jianzhong Cha
Publikationsdatum: 01.01.2015
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2015
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-013-9701-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2015

A structural transformation from p- to MSVL

Online unbounded batch scheduling on parallel machines with delivery times

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

Computing the shortest reset words of synchronizing automata

A combination of flow shop scheduling and the shortest path problem

Covering tree with stars

Premium Partner