Meny

Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Chips on wafers

Författare:
Publiceringsår: 2003
Språk: Engelska
Sidor: 412-423
Publikation/Tidskrift/Serie: Algorithms and data structures / Lecture notes in computer science
Volym: 2748
Dokumenttyp: Konferensbidrag
Förlag: Springer Berlin / Heidelberg

Sammanfattning

A set of rectangles S 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 S 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 S of rectangles and a real constant epsilon > 0 produces a grid packing of S whose area is at most (I + epsilon) times larger than an optimal packing in polynomial time. If epsilon 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 k less than or equal to n rectangles, and given a region A grid pack as many rectangles as possible within A. Apart from the approximation algorithms we present several hardness results.

Disputation

Nyckelord

  • Technology and Engineering

Övriga

8th International Workshop, WADS 2003
2003-07-30/2003-08-01
Ottawa, Ontario, Canada
Published
  • VR 2002-4049
Yes
  • ISSN: 0302-9743
  • ISBN: 978-3-540-40545-0

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen