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-\epsilon })\) and \(O(p^{1-\epsilon })\) non-approximability results even for \(n= 2\), as well as a \(\frac{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 \(\frac{p}{r}\)-approximation algorithm.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Crescenzi, P., Kann, V., Silvestri, R., Trevisan, L.: Structure in approximation classes. SIAM Journal on Computing 28(5), 1759–1782 (1999)
Cygan, M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 509–518. IEEE (2013)
Dokka, T., Bougeret, M., Boudet, V., Giroudeau, R., Spieksma, F.C.R.: Approximation algorithms for the wafer to wafer integration problem. In: Erlebach, T., Persiano, G. (eds.) WAOA 2012. LNCS, vol. 7846, pp. 286–297. Springer, Heidelberg (2013)
Dokka, T., Crama, Y., Spieksma, F.C.R.: Multi-dimensional vector assignment problems. Discrete Optimization 14, 111–125 (2014)
Duvillié, G., Bougeret, M., Boudet, V., Dokka, T., Giroudeau, R.: On the complexity of Wafer-to-Wafer Integration. Research report, Lirmm; UM II montpellier, Faculté des Sciences et Techniques du Languedoc, January 2015. HAL id:lirmm-01110027
Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-dimensional matching. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol. 2764, pp. 83–97. Springer, Heidelberg (2003)
Kratsch, S.: On polynomial kernels for integer linear programs: covering, packing and feasibility. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 647–658. Springer, Heidelberg (2013)
Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Mathematics of Operations Research 8(4), 538–548 (1983)
Niedermeier, R.: Invitation to fixed-parameter algorithms (2006)
Reda, S., Smith, G., Smith, L.: Maximizing the functional yield of wafer-to-wafer 3-d integration. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 17(9), 1357–1362 (2009)
Williamson, D.P., Shmoys, D.B.: The design of approximation algorithms. Cambridge University Press (2011)
Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 681–690. ACM (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Duvillié, G., Bougeret, M., Boudet, V., Dokka, T., Giroudeau, R. (2015). On the Complexity of Wafer-to-Wafer Integration. In: Paschos, V., Widmayer, P. (eds) Algorithms and Complexity. CIAC 2015. Lecture Notes in Computer Science(), vol 9079. Springer, Cham. https://doi.org/10.1007/978-3-319-18173-8_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-18173-8_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18172-1
Online ISBN: 978-3-319-18173-8
eBook Packages: Computer ScienceComputer Science (R0)