A large neighborhood search heuristic for the longest common subsequence problem

Given a set S={S ¹,…,S ^k } of finite strings, the k-Longest Common Subsequence Problem (k-LCSP) seeks a string L ^* of maximum length such that L ^* is a subsequence of each S ⁱ for i=1,…,k. This paper presents a large neighborhood search technique that provides quality solutions to large k-LCSP instances. This heuristic runs in linear time in both the length of the sequences and the number of sequences. Some computational results are provided.     

Repetition-free longest common subsequence

We study the following problem. Given two sequences x and y over a finite alphabet, find a repetition-free longest common subsequence of x and y. We show several algorithmic results, a computational complexity result, and we describe a preliminary experimental study based on the proposed algorithms. We also show that this problem is APX-hard.     

Efficient algorithms for the longest common subsequence problem with sequential substring constraints

In this paper, we generalize the inclusion constrained longest common subsequence (CLCS) problem to the hybrid CLCS problem which is the combination of the sequence inclusion CLCS and the string inclusion CLCS, called the sequential substring constrained longest common subsequence   (SSCLCS) problem. In the SSCLCS problem, we are given two strings A$A$ and B$B$ of lengths m$m$ and n$n$, respectively, formed by alphabet Σ$\Sigma$ and a constraint sequence C$C$ formed by ordered strings (C¹,C²,C³,…,C^l)$(C^1,C^2,C^3,\dots ,C^l)$ with total length r$r$. The problem is that of finding the longest common subsequence D$D$ of A$A$ and B$B$ containing C¹,C²,C³,…,C^l$C^1,C^2,C^3,\dots ,C^l$ as substrings and with the order of the C$C$’s retained. This problem has two variants, depending on whether the strings in C$C$ cannot overlap or may overlap. We propose algorithms with O(mnl+(m+n)(|Σ|+r))$O(mnl+(m+n)(\left|\Sigma \right|+r))$ and O(mnr+(m+n)|Σ|)$O(mnr+(m+n)\left|\Sigma \right|)$ time for the two variants. For the special case with one or two constraints, our algorithm runs in O(mn+(m+n)(|Σ|+r))$O(mn+(m+n)(\left|\Sigma \right|+r))$ or O(mnr+(m+n)|Σ|)$O(mnr+(m+n)\left|\Sigma \right|)$ time, respectively—an order faster than the algorithm proposed by Chen and Chao.     

A hybrid genetic algorithm for the repetition free longest common subsequence problem

Computing the longest common subsequence of two sequences is one of the most studied algorithmic problems. In this work we focus on a particular variant of the problem, called repetition free longest common subsequence (RF-LCS$\text{<small-caps>RF-LCS</small-caps>}$), which has been proved to be NP-hard. We propose a hybrid genetic algorithm, which combines standard genetic algorithms and estimation of distribution algorithms, to solve this problem. An experimental comparison with some well-known approximation algorithms shows the suitability of the proposed technique.     

Polynomial-time approximation schemes for packing and piercing fat objects

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem.