Chips on wafers (Extended abstract)

M. Andersson, J. Gudmundsson, C. Levcopoulos

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
1 Downloads (Pure)

Abstract

A set of rectangles is said to be grid packed if there exists a rectangular grid (not necessarily regular) such that every rectangle lies in the grid and there is at most one rectangle of in each cell. The area of a grid packing is the area of a minimal bounding box that contains all the rectangles in the grid packing. We present an approximation algorithm that given a set of rectangles and a real constant produces a grid packing of whose area is at most times larger than an optimal packing in polynomial time. If is chosen large enough the running time of the algorithm will be linear. We also study several interesting variants, for example the smallest area grid packing containing at least rectangles, and given a region grid pack as many rectangles as possible within . Apart from the approximation algorithms we present several hardness results.
Original languageEnglish
Title of host publicationAlgorithms and data structures : 8th international workshop, Ottawa, Ontario, Canada, July 30 - August 1, 2003 ; proceedings
EditorsM.H.M. Smid, J.R. Sack
Place of PublicationBerlin
PublisherSpringer
Pages412-423
ISBN (Print)3-540-40545-3
DOIs
Publication statusPublished - 2003

Publication series

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

Fingerprint

Dive into the research topics of 'Chips on wafers (Extended abstract)'. Together they form a unique fingerprint.

Cite this