## 2 Related Work
In the case of 2-MCSP, where each character can occur at most twice in each input string, the approximation of 3 is shown. For 4-MCSP the approximation ratio of the greedy algorithm is at least \(\Omega(\log\,n)\), and for the general problem they present an approximation ratio between \(\Omega(n^{0.43})\) and \(O(n^{0.69})\). An implication of this bound is that the \(\log(n)\)-approximation greedy algorithm presented in [PERSON] and [PERSON] [4] for a sub-family of strings cannot be extended to provide a \(\log(n)\)-approximation for all inputs. [PERSON] and [PERSON] [13] improve the lower bound on the approximation guarantee of the greedy algorithm for MCSP to \(\Omega(n^{0.46})\). [PERSON] _et al_. [6] present polynomial-time optimization algorithms for the edit distance problem which involves character insertions, character deletions, block copies and block deletions, when some restrictions are applied, such as allowing only left to right non recursive operations to be applied on the source string in order to get the target string. They refer to different versions of edit problems where internal copies (copy of a substring of the current string), external copies (copy of a substring of the original string), and shifted copies (copy of a shifted substring) are allowed. They also consider various costs of the operations such as constant, linear (the cost of a block operation is proportional to the length of the block) and nested costs (in which they allow the copied substring to be further edited). [PERSON] and [PERSON] [14] consider the case that \(S\) is a permutation of the integers 1 through \(n\), and give a 1.5 approximation algorithm for minimizing the number of moves needed to transform \(S\) into another permutation \(T\). The restriction that all characters are distinct makes the problem easier. [PERSON] and [PERSON] [15] compare two strings by extracting collections of substrings and placing them into the corresponding order. [PERSON] [16] considers block copies and looks for the minimal covering set of one string with respect to another. In [PERSON] [17], one can only swap a prefix or suffix of one chromosome with a prefix or suffix of another. [PERSON] _et al_. [18] consider the best _alignment_. There are several types of two-sequence alignments. The _global alignment_ is the traditional edit-distance, where the goal is to match the entire sequence. The _local alignment_ is to see whether a substring in one sequence aligns well with a substring in the other, thus, deleting prefixes or suffixes is free. The _semi-global alignment_ is when the input is constructed from two sequences, one short and one long, and the goal is to find whether the short one is a part of the long one. These variations are addressed by [PERSON] and [PERSON] [19]. In the alignment problem, the term _gap_ is used instead of a block deletion in the edit distance problem. A gap is a maximal consecutive run of spaces in a single string of a given alignment. The _affine gap penalty_ is when \(k\) consecutive deletions are not simply the cost of \(k\) individual single character deletions. The penalty combines the cost of opening a gap and \(k\) times the cost of extending a gap. Introduction of gaps into sequence alignments allows the alignment to be extended into regions where one sequence may have lost or gained sequence characters not found in the other. The gap penalty is used to help decide whether or not to accept a gap or insertion in an alignment when it is possible to achieve a good alignment at some other point in the sequence. When aligning two sequences it is often required to insert gaps in them in order to optimize the alignment. The classical algorithm for computing the similarity between two sequences uses a dynamic programming matrix, and compares two strings of size \(n\) in \(O(n^{2})\) time. [PERSON] and [PERSON] [2], apply the \"Four-Russians technique\" and reduce the running-time to \(O(n^{2}/\log\,n)\) by exploiting repetitions in the strings.