Skip to Main content Skip to Navigation

On the complexity of Wafer-to-Wafer Integration

Guillerme Duvillié 1 Marin Bougeret 1 Vincent Boudet 1 Trivikram Dokka 2 Rodolphe Giroudeau 1 
1 MAORE - Methods, Algorithms for Operations REsearch
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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 FPT when parameterized by p, and we use this FPT algorithm to improve the running time of the p r -approximation algorithm.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Guillerme DUVILLIE Connect in order to contact the contributor
Submitted on : Wednesday, January 28, 2015 - 10:29:11 AM
Last modification on : Friday, August 5, 2022 - 3:03:01 PM
Long-term archiving on: : Saturday, September 12, 2015 - 6:36:19 AM


Files produced by the author(s)


  • HAL Id : lirmm-01110027, version 1



Guillerme Duvillié, Marin Bougeret, Vincent Boudet, Trivikram Dokka, Rodolphe Giroudeau. On the complexity of Wafer-to-Wafer Integration. [Research Report] LIRMM. 2015. ⟨lirmm-01110027⟩



Record views


Files downloads