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

共 12 条

[1]

[Anonymous], P 1 ANN IEEE S PAR D

[2] Bin packing in multiple dimensions: Inapproximability results and approximation schemes [J].

Bansal, N ;

Correa, JR ;

Kenyon, C ;

Sviridenko, M .

MATHEMATICS OF OPERATIONS RESEARCH, 2006, 31 (01) :31-49

[3] Fast approximation schemes for two-stage, two-dimensional bin packing [J].

Caprara, A ;

Lodi, A ;

Monaci, M .

MATHEMATICS OF OPERATIONS RESEARCH, 2005, 30 (01) :150-172

[4] ON PACKING TWO-DIMENSIONAL BINS [J].

CHUNG, FRK ;

GAREY, MR ;

JOHNSON, DS .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (01) :66-76

[5]

CORREA JR, 2004, P 15 ACM SIAM S DISC, P179

[6] Online square and cube packing [J].

Epstein, L ;

van Stee, R .

ACTA INFORMATICA, 2005, 41 (09) :595-606

[7]

Garey MR, 1979, COMPUTER INTRACTABIL

[8] Approximation algorithms for orthogonal packing problems for hypercubes [J].

Harren, Rolf .

THEORETICAL COMPUTER SCIENCE, 2009, 410 (44) :4504-4532

[9] Multidimensional cube packing [J].

Kohayakawa, Y ;

Miyazawa, FK ;

Raghavan, P ;

Wakabayashi, Y .

ALGORITHMICA, 2004, 40 (03) :173-187

[10] PACKING SQUARES INTO A SQUARE [J].

LEUNG, JYT ;

TAM, TW ;

WONG, CS ;

YOUNG, GH ;

CHIN, FYL .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1990, 10 (03) :271-275

← 1 2 →