Optimal Tile Salvage.
Francine Berman, Frank Thomson Leighton, Lawrence Clement. Snyder · Purdue e-Pubs (Purdue University System) · 1981
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 lime algorithm is given for the 1 x 2 case, Le., 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.