Approximation algorithms for the wafer to wafer integration problem

T. Dokka; M. Bougeret; V. Boudet; R. Giroudeau; F.C.R. Spieksma

doi:10.1007/978-3-642-38016-7_23

Approximation algorithms for the wafer to wafer integration problem

T. Dokka
, M. Bougeret
, V. Boudet
, R. Giroudeau
, F.C.R. Spieksma

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

8 Citations (Scopus)

Abstract

Motivated by the yield optimization problem in semiconductor manufacturing, we model the wafer to wafer integration problem as a special multi-dimensional assignment problem (called WWI-m), and study it from an approximation point of view. We give approximation algorithms achieving an approximation factor of 3/2 and 4/3 for WWI-3, and we show that extensions of these algorithms to the case of arbitrary m do not give constant factor approximations. We argue that a special case of the yield optimization problem can be solved in polynomial time.

Original language	English
Title of host publication	Approximation and Online Algorithms : 10th International Workshop, WAOA 2012, Revised Selected Papers
Editors	Thomas Erlebach, Giuseppe Persiano
Place of Publication	Berlin
Publisher	Springer
Pages	286-297
Number of pages	12
ISBN (Electronic)	978-3-642-38016-7
ISBN (Print)	978-3-642-38015-0
DOIs	https://doi.org/10.1007/978-3-642-38016-7_23
Publication status	Published - 2013
Externally published	Yes
Event	10th International Workshop on Approximation and Online Algorithms (WAOA 2012) - Ljubljana, Slovenia Duration: 13 Sept 2012 → 14 Sept 2012 Conference number: 10

Publication series

Name	Lecture Notes in Computer Science
Volume	7846
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Workshop on Approximation and Online Algorithms (WAOA 2012)
Abbreviated title	WOA 2012
Country/Territory	Slovenia
City	Ljubljana
Period	13/09/12 → 14/09/12

Keywords

Approximation
Computational complexity
Efficient algorithm
Wafer-to-wafer integration

Access to Document

10.1007/978-3-642-38016-7_23

Cite this

Dokka, T., Bougeret, M., Boudet, V., Giroudeau, R., & Spieksma, F. C. R. (2013). Approximation algorithms for the wafer to wafer integration problem. In T. Erlebach, & G. Persiano (Eds.), Approximation and Online Algorithms : 10th International Workshop, WAOA 2012, Revised Selected Papers (pp. 286-297). (Lecture Notes in Computer Science; Vol. 7846). Springer. https://doi.org/10.1007/978-3-642-38016-7_23

@inproceedings{602213189c1545798063dbd55b3583f9,

title = "Approximation algorithms for the wafer to wafer integration problem",

abstract = "Motivated by the yield optimization problem in semiconductor manufacturing, we model the wafer to wafer integration problem as a special multi-dimensional assignment problem (called WWI-m), and study it from an approximation point of view. We give approximation algorithms achieving an approximation factor of 3/2 and 4/3 for WWI-3, and we show that extensions of these algorithms to the case of arbitrary m do not give constant factor approximations. We argue that a special case of the yield optimization problem can be solved in polynomial time.",

keywords = "Approximation, Computational complexity, Efficient algorithm, Wafer-to-wafer integration",

author = "T. Dokka and M. Bougeret and V. Boudet and R. Giroudeau and F.C.R. Spieksma",

year = "2013",

doi = "10.1007/978-3-642-38016-7\_23",

language = "English",

isbn = "978-3-642-38015-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "286--297",

editor = "Erlebach, \{Thomas \} and Giuseppe Persiano",

booktitle = "Approximation and Online Algorithms : 10th International Workshop, WAOA 2012, Revised Selected Papers",

address = "Germany",

note = "10th International Workshop on Approximation and Online Algorithms (WAOA 2012), WOA 2012 ; Conference date: 13-09-2012 Through 14-09-2012",

}

Dokka, T, Bougeret, M, Boudet, V, Giroudeau, R & Spieksma, FCR 2013, Approximation algorithms for the wafer to wafer integration problem. in T Erlebach & G Persiano (eds), Approximation and Online Algorithms : 10th International Workshop, WAOA 2012, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7846, Springer, Berlin, pp. 286-297, 10th International Workshop on Approximation and Online Algorithms (WAOA 2012), Ljubljana, Slovenia, 13/09/12. https://doi.org/10.1007/978-3-642-38016-7_23

Approximation algorithms for the wafer to wafer integration problem. / Dokka, T.; Bougeret, M.; Boudet, V. et al.
Approximation and Online Algorithms : 10th International Workshop, WAOA 2012, Revised Selected Papers. ed. / Thomas Erlebach; Giuseppe Persiano. Berlin: Springer, 2013. p. 286-297 (Lecture Notes in Computer Science; Vol. 7846).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximation algorithms for the wafer to wafer integration problem

AU - Dokka, T.

AU - Bougeret, M.

AU - Boudet, V.

AU - Giroudeau, R.

AU - Spieksma, F.C.R.

N1 - Conference code: 10

PY - 2013

Y1 - 2013

N2 - Motivated by the yield optimization problem in semiconductor manufacturing, we model the wafer to wafer integration problem as a special multi-dimensional assignment problem (called WWI-m), and study it from an approximation point of view. We give approximation algorithms achieving an approximation factor of 3/2 and 4/3 for WWI-3, and we show that extensions of these algorithms to the case of arbitrary m do not give constant factor approximations. We argue that a special case of the yield optimization problem can be solved in polynomial time.

AB - Motivated by the yield optimization problem in semiconductor manufacturing, we model the wafer to wafer integration problem as a special multi-dimensional assignment problem (called WWI-m), and study it from an approximation point of view. We give approximation algorithms achieving an approximation factor of 3/2 and 4/3 for WWI-3, and we show that extensions of these algorithms to the case of arbitrary m do not give constant factor approximations. We argue that a special case of the yield optimization problem can be solved in polynomial time.

KW - Approximation

KW - Computational complexity

KW - Efficient algorithm

KW - Wafer-to-wafer integration

UR - https://www.scopus.com/pages/publications/84894121882

U2 - 10.1007/978-3-642-38016-7_23

DO - 10.1007/978-3-642-38016-7_23

M3 - Conference contribution

AN - SCOPUS:84894121882

SN - 978-3-642-38015-0

T3 - Lecture Notes in Computer Science

SP - 286

EP - 297

BT - Approximation and Online Algorithms : 10th International Workshop, WAOA 2012, Revised Selected Papers

A2 - Erlebach, Thomas

A2 - Persiano, Giuseppe

PB - Springer

CY - Berlin

T2 - 10th International Workshop on Approximation and Online Algorithms (WAOA 2012)

Y2 - 13 September 2012 through 14 September 2012

ER -

Dokka T, Bougeret M, Boudet V, Giroudeau R, Spieksma FCR. Approximation algorithms for the wafer to wafer integration problem. In Erlebach T, Persiano G, editors, Approximation and Online Algorithms : 10th International Workshop, WAOA 2012, Revised Selected Papers. Berlin: Springer. 2013. p. 286-297. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-38016-7_23

Approximation algorithms for the wafer to wafer integration problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this