2013 | OriginalPaper | Buchkapitel
Packing Cubes into a Cube Is NP-Hard in the Strong Sense
verfasst von : Yiping Lu, Danny Z. Chen, Jianzhong Cha
Erschienen in: Computing and Combinatorics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
> 2) problems of packing hypercubes into a hypercube remains an open question [5,7]. In this paper, we show that the three-dimensional problem version of packing cubes into a cube is NP-hard in the strong sense.