Home > Research > Publications & Outputs > Approximation algorithms for the wafer to wafer...
View graph of relations

Approximation algorithms for the wafer to wafer integration problem

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Published
  • Trivikram Dokka
  • Marin Bougeret
  • Vincent Boudet
  • Rodolphe Giroudeau
  • Frits C.R. Spieksma
Close
Publication date2013
Host publicationApproximation and Online Algorithms: 10th International Workshop, WAOA 2012, Ljubljana, Slovenia, September 13-14, 2012, Revised Selected Papers
EditorsThomas Erlebach, Giuseppe Persiano
Place of PublicationBerlin
PublisherSpringer-Verlag
Pages286-297
Number of pages12
Volume7846
ISBN (electronic)9783642380167
ISBN (print)9783642380150
<mark>Original language</mark>English

Publication series

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

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.