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 - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 ORSTAT - Operations Research and Business Statistics
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.
Type de document :
Communication dans un congrès
CIAC: International Conference on Algorithms and Complexity, May 2015, Paris, France. 9th International Conference on Algorithms and Complexity, LNCS (9079), pp.208-220, 2015, Algorithms and Complexity. 〈10.1007/978-3-319-18173-8_15〉
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01250989
Contributeur : Rodolphe Giroudeau <>
Soumis le : mardi 5 janvier 2016 - 14:52:45
Dernière modification le : mercredi 18 juillet 2018 - 11:52:05

Lien texte intégral

openaccess

Identifiants

Collections

MAORE | LIRMM | MIPS | UNIV-MONTPELLIER

Citation

Guillerme Duvillié, Marin Bougeret, Vincent Boudet, Trivikram Dokka, Rodolphe Giroudeau. On the Complexity of Wafer-to-Wafer Integration. CIAC: International Conference on Algorithms and Complexity, May 2015, Paris, France. 9th International Conference on Algorithms and Complexity, LNCS (9079), pp.208-220, 2015, Algorithms and Complexity. 〈10.1007/978-3-319-18173-8_15〉. 〈lirmm-01250989〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

87

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD