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(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.
Type de document :
Rapport
[Research Report] LIRMM. 2015
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01110027
Contributeur : Guillerme Duvillie <>
Soumis le : mercredi 28 janvier 2015 - 10:29:11
Dernière modification le : mercredi 18 juillet 2018 - 11:52:05
Document(s) archivé(s) le : samedi 12 septembre 2015 - 06:36:19

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01110027, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

153

Téléchargements de fichiers

193