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 条
  • [21] A simplified NP-complete MAXSAT problem
    Raman, V
    Ravikumar, B
    Rao, SS
    INFORMATION PROCESSING LETTERS, 1998, 65 (01) : 1 - 6
  • [22] Universal solutions for NP-complete problems
    Portier, N
    THEORETICAL COMPUTER SCIENCE, 1998, 201 (1-2) : 137 - 150
  • [23] MaxCut on permutation graphs is NP-complete
    de Figueiredo, Celina M. H.
    de Melo, Alexsander A.
    Oliveira, Fabiano S.
    Silva, Ana
    JOURNAL OF GRAPH THEORY, 2023, 104 (01) : 5 - 16
  • [24] Finding smooth maps NP-complete
    Poland, J
    INFORMATION PROCESSING LETTERS, 2003, 85 (05) : 249 - 253
  • [25] Splitting NP-complete sets infinitely
    Zhang, Liyu
    Quweider, Mahmoud
    Khan, Fitra
    Lei, Hansheng
    INFORMATION PROCESSING LETTERS, 2024, 186
  • [26] Medical diagnosis and treatment is NP-complete
    Arle, Jeffrey. E.
    Carlson, Kristen W.
    JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE, 2021, 33 (02) : 297 - 312
  • [27] New NP-complete partition problems
    Saeednia, S
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2002, 48 (07) : 2092 - 2094
  • [28] Satogaeri, Hebi and Suraromu are NP-Complete
    Kanehiro, Shohei
    Takenaga, Yasuhiko
    3RD INTERNATIONAL CONFERENCE ON APPLIED COMPUTING AND INFORMATION TECHNOLOGY (ACIT 2015) 2ND INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE AND INTELLIGENCE (CSI 2015), 2015, : 46 - 51
  • [29] An NP-complete fragment of fibring logic
    Wu, Yin
    Jiang, Min
    Huang, Zhongqiang
    Chao, Fei
    Zhou, Changle
    ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2015, 75 (3-4) : 391 - 417
  • [30] Five Cells and Tilepaint are NP-Complete
    Iwamoto, Chuzo
    Ide, Tatsuya
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2022, E105D (03) : 508 - 516
12345