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 条
  • [1] Packing cubes into a cube is NP-complete in the strong sense
    Yiping Lu
    Danny Z. Chen
    Jianzhong Cha
    Journal of Combinatorial Optimization, 2015, 29 : 197 - 215
  • [2] TETRAVEX is NP-complete
    Takenaga, Yasuhiko
    Walsh, Toby
    INFORMATION PROCESSING LETTERS, 2006, 99 (05) : 171 - 174
  • [3] Autoreducibility of NP-Complete Sets under Strong Hypotheses
    John M. Hitchcock
    Hadi Shafei
    computational complexity, 2018, 27 : 63 - 97
  • [4] Autoreducibility of NP-Complete Sets under Strong Hypotheses
    Hitchcock, John M.
    Shafei, Hadi
    COMPUTATIONAL COMPLEXITY, 2018, 27 (01) : 63 - 97
  • [5] Autoreducibility of NP-Complete Sets
    Hitchcock, John M.
    Shafei, Hadi
    33RD SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2016), 2016, 47
  • [6] Hashiwokakero is NP-complete
    Andersson, Daniel
    INFORMATION PROCESSING LETTERS, 2009, 109 (19) : 1145 - 1146
  • [7] Shellability is NP-complete
    Goaoc, Xavier
    Patak, Pavel
    Patakova, Zuzana
    Tancer, Martin
    Wagner, Uli
    JOURNAL OF THE ACM, 2019, 66 (03)
  • [8] BLOCKSUM is NP-Complete
    Haraguchi, Kazuya
    Ono, Hirotaka
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2013, E96D (03) : 481 - 488
  • [9] Two-segmented channel routing is strong NP-complete
    Li, WN
    DISCRETE APPLIED MATHEMATICS, 1997, 78 (1-3) : 291 - 298
  • [10] Packing Cubes into a Cube in (D>3)-Dimensions
    Lu, Yiping
    Chen, Danny Z.
    Cha, Jianzhong
    COMPUTING AND COMBINATORICS, 2015, 9198 : 264 - 276
12345