On the Complexity of Wafer-to-Wafer Integration

摘要

In this paper we consider the Wafer-to-Wafer Integration problem. A wafer is a p-dimensional binary vector. The input of this problem is described by m disjoints sets (called "lots"), where each set 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 O(m(1-∈)) and O(p~(1-∈)) non-approximability results even for n = 2, as well as a p/r-approximation algorithm for any constant r. Finally, we show that the problem is FPTwhen parameterized by p, and we use this FPTalgorithm to improve the running time of the p/r-approximation algorithm.