Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Chips on wafers

In English

Författare

Summary, in English

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.

Avdelning/ar

  • Computer Science

Publiceringsår

2003

Språk

Engelska

Sidor

412-423

Publikation/Tidskrift/Serie

Lecture Notes in Computer Science

Volym

2748

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • Computer Science

Conference name

8th International Workshop, WADS 2003

Conference date

2003-07-30 - 2003-08-01

Conference place

Ottawa, Ontario, Canada

Status

Published

Projekt

  • VR 2002-4049

ISBN/ISSN/Övrigt

  • ISSN: 1611-3349
  • ISSN: 0302-9743
  • ISBN: 978-3-540-40545-0