【摘 要】
:
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 wis
【机 构】
:
Florian Diedrich,Max-Planck-Institut fur Informatik,Department of Computer Science
论文部分内容阅读
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