Packing cubes into a cube is NP-complete in the strong sense
| Autor: | Danny Z. Chen, Yiping Lu, Jianzhong Cha |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
Control and Optimization Bin packing problem Applied Mathematics Square (algebra) Computer Science Applications Combinatorics Packing problems Square packing in a square Packing dimension Computational Theory and Mathematics Set packing Discrete Mathematics and Combinatorics Tetrahedron packing Hypercube Mathematics |
| Zdroj: | Journal of Combinatorial Optimization. 29:197-215 |
| ISSN: | 1573-2886 1382-6905 |
| DOI: | 10.1007/s10878-013-9701-1 |
| Popis: | 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 $$ d ? 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink