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

被引：2
|
作者：
Lu, Yiping [1 ]
Chen, Danny Z. [2 ]
Cha, Jianzhong [1 ]
机构：
[1] Beijing Jiaotong Univ, Sch Mech Elect & Control Engn, Beijing 100044, Peoples R China
[2] Univ Notre Dame, Dept Comp Sci & Engn, Notre Dame, IN 46556 USA
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2015年 / 29卷 / 01期
基金：
美国国家科学基金会;
关键词：
Computational complexity; Packing problems; Cube packing; Bin packing; NP-completeness;
D O I：
10.1007/s10878-013-9701-1
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
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 >= 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.
引用
收藏
页码：197 / 215
页数：19
相关论文
共 50 条
12345