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 条
  • [31] The minimal logically-defined NP-complete problem
    Barbanchon, R
    Grandjean, E
    STACS 2004, PROCEEDINGS, 2004, 2996 : 338 - 349
  • [32] CLIQUE-WIDTH IS NP-COMPLETE
    Fellows, Michael R.
    Rosamond, Frances A.
    Rotics, Udi
    Szeider, Stefan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (02) : 909 - 939
  • [33] Optimal Jacobian accumulation is NP-complete
    Naumann, Uwe
    MATHEMATICAL PROGRAMMING, 2008, 112 (02) : 427 - 441
  • [34] Computing quantum discord is NP-complete
    Huang, Yichen
    NEW JOURNAL OF PHYSICS, 2014, 16
  • [35] Optimal Jacobian accumulation is NP-complete
    Uwe Naumann
    Mathematical Programming, 2008, 112 : 427 - 441
  • [36] An NP-complete fragment of fibring logic
    Yin Wu
    Min Jiang
    Zhongqiang Huang
    Fei Chao
    Changle Zhou
    Annals of Mathematics and Artificial Intelligence, 2015, 75 : 391 - 417
  • [37] Minimum Manhattan Network is NP-Complete
    Chin, Francis Y. L.
    Guo, Zeyu
    Sun, He
    DISCRETE & COMPUTATIONAL GEOMETRY, 2011, 45 (04) : 701 - 722
  • [38] The coherence of Lukasiewicz assessments is NP-complete
    Bova, Simone
    Flaminio, Tommaso
    INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, 2010, 51 (03) : 294 - 304
  • [39] Perfectly packing a cube by cubes of nearly harmonic sidelength
    McClenagan, Rory
    CANADIAN MATHEMATICAL BULLETIN-BULLETIN CANADIEN DE MATHEMATIQUES, 2023, 66 (03): : 1061 - 1071
  • [40] FINDING HAMILTONIAN CIRCUITS IN ARRANGEMENTS OF JORDAN CURVES IS NP-COMPLETE
    IWAMOTO, C
    TOUSSAINT, GT
    INFORMATION PROCESSING LETTERS, 1994, 52 (04) : 183 - 189
12345