On the complexity of Wafer-to-Wafer Integration

DO Vol. 22, p. 255 - 269

Journal - Discrete Optimization (2016)

Authors: Vincent Boudet and Marin Bougeret and Trivikram Dokka and Guillerme Duvillié and Rodolphe Giroudeau

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 $m^{1−\varepsilon}$ and $p^{1−\varepsilon}$ non-approximability results even for $n=2$, $f(n)$ non-approximability for any polynomial-time computable function $f$, as well as a $\frac{p}{r}$-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 $\frac{p}{r}$-approximation algorithm.