There is no asymptotic PTAS for two-dimensional vector packing

被引:81
作者
Woeginger, GJ [1 ]
机构
[1] Graz Tech Univ, Inst Math, A-8010 Graz, Austria
关键词
analysis of algorithms; combinatorial problems; worst case analysis; approximation algorithm; approximation scheme; vector packing; bin packing;
D O I
10.1016/S0020-0190(97)00179-8
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
The d-dimensional vector packing problem is a wall-known generalization of the classical bin packing problem: For a given list of vectors in [0, 1](d), the goal is to partition the list into the minimum number of subsets, such that in every subset the sum of all vectors is at most one in every coordinate. For the case d = 1, Fernandez de la Vega and Lueker (1981) designed an asymptotic polynomial time approximation scheme. In this note we prove that already for the case d = 2, the existence of an asymptotic polynomial time approximation scheme would imply P = NP. The proof is very simple and uses no new ideas. (C) 1997 Elsevier Science B.V.
引用
收藏
页码:293 / 297
页数:5
相关论文
共 10 条
[1]  
ALON N, 1996, LECT NOTES COMPUTER, V1136, P406
[2]  
[Anonymous], ALGORITHMICA
[3]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[4]  
ARORA S, 1997, APPROXIMATION ALGORI, pCH10
[5]   ON PACKING TWO-DIMENSIONAL BINS [J].
CHUNG, FRK ;
GAREY, MR ;
JOHNSON, DS .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (01) :66-76
[6]  
DELAVEGA WF, 1981, COMBINATORICA, V1, P349
[7]   RESOURCE CONSTRAINED SCHEDULING AS GENERALIZED BIN PACKING [J].
GAREY, MR ;
GRAHAM, RL ;
JOHNSON, DS ;
YAO, ACC .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1976, 21 (03) :257-298
[8]   MAXIMUM BOUNDED 3-DIMENSIONAL MATCHING IS MAX SNP-COMPLETE [J].
KANN, V .
INFORMATION PROCESSING LETTERS, 1991, 37 (01) :27-35
[9]   MULTIDIMENSIONAL BIN PACKING ALGORITHMS [J].
KOU, LT ;
MARKOWSKY, G .
IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1977, 21 (05) :443-448
[10]   NEW ALGORITHMS FOR BIN PACKING [J].
YAO, ACC .
JOURNAL OF THE ACM, 1980, 27 (02) :207-227