Approximation algorithms for maximum two-dimensional pattern matching.
Srinivasa Rao ArikatiAnders DessmarkAndrzej LingasMadhav V. MarathePublished in: Theor. Comput. Sci. (2001)
Keyphrases
- pattern matching
- approximation algorithms
- np hard
- special case
- worst case
- approximation ratio
- pattern matching algorithm
- minimum cost
- vertex cover
- tree matching
- regular expressions
- matching process
- randomized algorithms
- string matching
- open shop
- primal dual
- precedence constraints
- multi dimensional
- disjoint paths
- set cover
- constant factor
- integrality gap
- boyer moore
- approximation schemes
- combinatorial auctions
- scheduling problem
- approximate pattern matching
- constant factor approximation