Open AccessApproximation algorithms for maximum two-dimensional pattern matching
Author(s) -
Srinivasa Rao Arikati,
Anders Dessmark,
Andrzej Lingas,
Madhav Marathe
Publication year - 1996
Language(s) - English
Resource type - Reports
DOI - 10.2172/248298
Subject(s) - pattern matching , matching (statistics) , approximation algorithm , algorithm , 3 dimensional matching , mathematics , combinatorics , computer science , blossom algorithm , artificial intelligence , statistics
We introduce the following optimization version of the classical pattern matching problem (referred to as the maximum pattern matching problem). Given a two-dimensional rectangular text and a 2- dimensional rectangular pattern find the maximum number of non- overlapping occurrences of the pattern in the text. Unlike the classical 2-dimensional pattern matching problem, the maximum pattern matching problem is NP - complete. We devise 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