The central problem of text processing is pattern matching: given two strings (a pattern and a text), find all fragments of the text matching the pattern. In exact matching, solely equal strings match; however, this condition is relaxed in many variants of approximate pattern matching. In the k-mismatch problem, we allow for up to k substitutions, that is, strings of the same length are assumed to match even if there are at most k mismatching characters between them.
Conferences
A Subquadratic Approximation Scheme for Partition
The Subset Sum problem is one of the most fundamental problem in theoretical computer science. One is given a set S of n integers and an integer t. The problem is to determine if there exists a subset of S with total sum equal exactly t.
Eight papers co-authored by our colleagues at the Institute of Informatics of University of Warsaw have been accepted to SIAM Symposium on Discrete Algorithms