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 proceedingConference contributionAcademicpeer-review

7 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 languageEnglish
Title of host publicationApproximation and Online Algorithms : 10th International Workshop, WAOA 2012, Revised Selected Papers
EditorsThomas Erlebach, Giuseppe Persiano
Place of PublicationBerlin
PublisherSpringer
Pages286-297
Number of pages12
ISBN (Electronic)978-3-642-38016-7
ISBN (Print)978-3-642-38015-0
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event10th International Workshop on Approximation and Online Algorithms (WAOA 2012) - Ljubljana, Slovenia
Duration: 13 Sep 201214 Sep 2012
Conference number: 10

Publication series

NameLecture Notes in Computer Science
Volume7846
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Workshop on Approximation and Online Algorithms (WAOA 2012)
Abbreviated titleWOA 2012
CountrySlovenia
CityLjubljana
Period13/09/1214/09/12

Keywords

  • Approximation
  • Computational complexity
  • Efficient algorithm
  • Wafer-to-wafer integration

Fingerprint Dive into the research topics of 'Approximation algorithms for the wafer to wafer integration problem'. Together they form a unique fingerprint.

Cite this