Home > Research > Publications & Outputs > On the complexity of wafer-to-wafer integration

Research

Associated organisational units

Electronic data

  • CIAC2015

    Rights statement: The final, definitive version of this article has been published in CIAC2015, LNCS 9079.

    Accepted author manuscript, 508 KB, PDF document

    Available under license: CC BY-NC

Links

Text available via DOI:

View graph of relations

On the complexity of wafer-to-wafer integration

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Published
Close
More...
Publication date16/05/2015
Host publicationAlgorithms and Complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings
EditorsVangelis Th. Paschos, Peter Widmayer
Place of PublicationCham
PublisherSpringer
Pages208-220
Number of pages13
ISBN (electronic)9783319181738
ISBN (print)9783319181721
<mark>Original language</mark>English

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9079
ISSN (Print)0302-9743

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 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.