@inproceedings{f565a00b9c7b4a5f95788b41c9a3d317,

title = "On the Complexity of Wafer-to-Wafer Integration",

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(m1−ϵ) and O(p1−ϵ) non-approximability results even for n=2 , 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.",

author = "Guillerme Duvilli{\'e} and Marin Bougeret and Vincent Boudet and Trivikram Dokka and Rodolphe Giroudeau",

year = "2015",

month = may,

day = "16",

doi = "10.1007/978-3-319-18173-8_15",

language = "English",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "208--220",

editor = "Paschos, {Vangelis Th. } and { Widmayer}, Peter",

booktitle = "Algorithms and Complexity. 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings",

}