Optimal Tile Salvage.

Abstract

A map is a tiling of a finite region of the plane with unit squares such that some tiles have been removed. The optimal x x y-Tile Salvage Problem is: Given a map, find the maximum number of non-overlapping x x y tiled rectangles. A polynomial time algorithm is given for the 1 x 2 case, i.e., adjacent pairs. It is shown that the problem is NP-complete for the 2 x 2 case. A polynomial time algorithm is presented for finding 2 x 2 groups that is no worse than one half optimal. The problem is motivated by a technique for increasing the size of very large scale integrated (VLSI) circuit chips. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1982
Accession Number
ADA119117

Entities

People

  • Francine Berman
  • Frank Thomson Leighton
  • Lawrence H Snyder

Organizations

  • Purdue University

Tags

Communities of Interest

  • Advanced Electronics
  • Air Platforms
  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computer Science
  • Construction
  • Contracts
  • Coverings
  • Engineering
  • Generators
  • Information Processing
  • Information Systems
  • Massachusetts
  • Military Research
  • Polynomials
  • Security
  • Transmission Lines
  • Two Dimensional
  • Universities

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Graph Algorithms and Convex Optimization.
  • Integrated Circuit Design and Technology.