Approximation Algorithms for 3D Orthogonal Knapsack

来源 :计算机科学技术学报(英文版) | 被引量 : 0次 | 上传用户:cloudyliu
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9 + ∈ and 8 + ∈, as well as an algorithm with approximation ratio 7 + ∈ that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 + ∈ and 5 + ∈, respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29/4, improving the previously best known result of 45/4.
其他文献
As an important intermediate to study cyclin-dependent kinase (CDK) inhibitors, 2-aryl-8-(piperidin-4-yl)-5,7-dimethoxy-4H-chromen-4-one derivatives were prepar
Two complexes CuLCl(H2O) 1 and Ni(L)2 2 (HL = 2-carboxy-1,10-phenanthroline) have been synthesized and characterized by single-crystal X-ray crystallography. Th
Three new anthranilic acid derivatives, N-heneicosanoylanthranilic acid (1b), N-tricosanoylanthranilic acid (1d), N-tetra-cosanoylanthranilic acid (1e), and two
In this paper,crystallization kinetics of a series of ethylene-propylene copolymers prepared by living polymerization coordination catalyzed by a fluorinated bi
The mechanism, catalytic effect and substituent effect of the hetero-Diels-Alder reactions between phosphonodithioformate and butadienes have been investigated
4(3H)-Quinazolinones have been synthesized from poly(ethylene glycol) (PEG) supported aza-Wittig reaction. 2-Dialkylamino-4(3H)-quinazolinones 6 were synthesize
A series of new nickel(II)complexes with 2-aminomethylpyridine igands.(2-PyCH2NHAr)2,NiBr2(Ar=2.6-dimethylphenyl 2a;2,6-diisopropylphenyl 2b,2,6-difluorophenyl
A cyclic bimetallic metal-organic complex [Zn(Cl)(H-fmpdc)(H2O)]2·2H2O (fmpdc = 4-(furan-2-yl)-2,6-dimethylpyridine-3,5-dicarboxylate) was synthesized and char
One new compound, ilexlignan A (1), was isolated from the root of llex pubescens. Its structure was elucidated by thecombination of one- and two-dimensional NMR
Two novel mononaphthalimide homospermidine derivatives (2a, 2b) with three or four methylene unit as linkages weresynthesized and evaluated for cytotoxicity aga