کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5128278 | 1378587 | 2016 | 15 صفحه PDF | دانلود رایگان |
In this paper we consider the Wafer-to-Wafer Integration problem. A wafer can be seen as a p-dimensional binary vector. The input of this problem is described by m multisets (called “lots”), where each multiset contains n wafers. The output of the problem is a set of n disjoint stacks, where a stack is a set of m wafers (one wafer from each lot). To each stack we associate a p-dimensional binary vector corresponding to the bit-wise AND operation of the wafers of the stack. The objective is to maximize the total number of “1” in the n stacks. We provide m1âϵ and p1âϵ non-approximability results even for n=2, f(n) non-approximability for any polynomial-time computable function f, as well as a pr-approximation algorithm for any constant r. Finally, we show that the problem is FPT when parameterized by p, and we use this FPT algorithm to improve the running time of the pr-approximation algorithm.
Journal: Discrete Optimization - Volume 22, Part B, November 2016, Pages 255-269