Approximation algorithms for maximum two-dimensional pattern matching

We introduce the following optimization version of the classical pattern ma tching problem (referred to as the maximum pattern matching problem). Given a two-dimensional rectangular text and a two-dimensional rectangular patte rn, find the maximum number of non-overlapping occurrences of the pattern i n the text. Unlike the classical two-dimensional pattern matching problem, the maximum two-dimensional pattern matching problem is NP-complete. We dev ise polynomial time approximation algorithms and approximation schemes for this problem. We also briefly discuss how the approximation algorithms can be extended to include a number of other variants of the problem. (C) 2001 Elsevier Science B.V. All rights reserved.