Faster algorithms for computing longest common increasing subsequences

We present algorithms for finding a longest common increasing subsequence of two or more input sequences. For two sequences of lengths n and m, where m?n, we present an algorithm with an output-dependent expected running time of and O(m) space, where ? is the length of an LCIS, σ is the size of the alphabet, and Sort is the time to sort each input sequence. For k?3 length-n sequences we present an algorithm which improves the previous best bound by more than a factor k for many inputs. In both cases, our algorithms are conceptually quite simple but rely on existing sophisticated data structures. Finally, we introduce the problem of longest common weakly-increasing (or non-decreasing) subsequences (LCWIS), for which we present an -time algorithm for the 3-letter alphabet case. For the extensively studied longest common subsequence problem, comparable speedups have not been achieved for small alphabets.     

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.     

Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds

In this paper the problem of optimally guillotine cutting a rectangle (A, B  ) into small rectangles of two kinds is considered. Rectangles of the first kind (c,_ai),i∈I$(c\text{,}{a}_i)\text{,}i\in I$ have the same width, and their heights can be various. Rectangles of the second kind (_bj,d),j∈J$(b_j\text{,}d)\text{,}j\in J$ have the same height, and their widths can be various. The number of occurrences of each small rectangle in a cutting pattern is not restricted. Similar problems often appear in the furniture industry. This cutting problem is reduced to the shortest path problem in a special rectangular grid, for which a linear time algorithm is suggested. This approach generalizes the approach of [E. Girlich, A.G. Tarnowski, On polynomial solvability of two multiprocessor scheduling problems, Mathematical Methods of Operations Research 50 (1999) 27–51; A.G. Tarnowski, Advanced polynomial time algorithm for guillotine generalized pallet loading problem, in: The International Scientific Collection: Decision Making Under Conditions of Uncertainty (Cutting-Packing Problems), Ufa State Aviation Technical University, 1997, pp. 93–124] and allows us to construct polynomial algorithms for the guillotine cutting problem considered with a fixed number of small rectangles of two kinds.     

Repetition-free longest common subsequence

We study the problem of, given two finite sequences x and y, finding a repetition-free longest common subsequence of x and y. We show some algorithmic results, a complexity result, and a preliminary experimental study based on the proposed algorithms.     

Iterated greedy local search methods for unrelated parallel machine scheduling

This work deals with the parallel machine scheduling problem which consists in the assignment of n jobs on m   parallel machines. The most general variant of this problem is when the processing time depends on the machine to which each job is assigned to. This case is known as the unrelated parallel machine problem. Similarly to most of the literature, this paper deals with the minimization of the maximum completion time of the jobs, commonly referred to as makespan (_Cmax)$(C_{\text{max}})$. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated procedures. By contrast, in this paper we propose a set of simple iterated greedy local search based metaheuristics that produce solutions of very good quality in a very short amount of time. Extensive computational campaigns show that these solutions are, most of the time, better than the current state-of-the-art methodologies by a statistically significant margin.     

A new solution method for the finite-horizon discrete-time EOQ problem

We consider the finite-horizon discrete-time economic order quantity problem. Kovalev and Ng (2008) have developed a solution approach for solving this problem. Their approach requires a search for the optimal number of orders, which takes O(logn)$\text{O}(\log n)$ time. In this note, we present a modified solution method, which can determine the optimal solution without the need of such a search.     

Quasi-polynomial tractability of linear problems in the average case setting

We study d$d$-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For the absolute error criterion, we obtain the necessary and sufficient conditions in terms of the eigenvalues of its covariance operator and obtain an estimate of the exponent t^qpol-avg$t^{\text{qpol-avg}}$ of quasi-polynomial tractability which cannot be improved in general. For the linear tensor product problems, we find that the quasi-polynomial tractability is equivalent to the strong polynomial tractability. For the normalized error criterion, we solve a problem related to the Korobov kernels, which is left open in Lifshits et al. (2012).     

An all-substrings common subsequence algorithm

Given two strings A and B of lengths n_a and n_b, n_a?n_b, respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B^′ of B, the length of the longest string that is a subsequence of both A and B^′. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm to prepare the basic data structure for ALCS queries that takes O(n_an_b) time and O(n_a+n_b) space. After this preparation, it is possible to build a matrix of size that allows any LCS length to be retrieved in constant time. Some trade-offs between the space required and the querying time are discussed. To our knowledge, this is the first algorithm in the literature for the ALCS problem.     

Polar permutation graphs are polynomial-time recognisable

Polar graphs generalise bipartite graphs, cobipartite graphs, and split graphs, and they constitute a special type of matrix partitions. A graph is polar if its vertex set can be partitioned into two, such that one part induces a complete multipartite graph and the other part induces a disjoint union of complete graphs. Deciding whether a given arbitrary graph is polar, is an NP$\text{NP}$-complete problem. Here, we show that for permutation graphs this problem can be solved in polynomial time. The result is surprising, as related problems like achromatic number and cochromatic number are NP$\text{NP}$-complete on permutation graphs. We give a polynomial-time algorithm for recognising graphs that are both permutation and polar. Prior to our result, polarity has been resolved only for chordal graphs and cographs.     

Convergence theorems of common elements for equilibrium problems and fixed point problems in Banach spaces

The purpose of this paper is to introduce hybrid projection algorithms for finding a common element of the set of common fixed points of two quasi-?$?$-nonexpansive mappings and the set of solutions of an equilibrium problem in the framework of Banach spaces. Our results improve and extend the corresponding results announced by many others.     

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.     

Faster subsequence recognition in compressed strings

Computation on compressed strings is one of the key approaches to processing massive data sets. We consider local subsequence recognition problems on strings compressed by straight-line programs (SLP), which is closely related to Lempel–Ziv compression. For an SLP-compressed text of length , and an uncompressed pattern of length n, Cégielski et al. gave an algorithm for local subsequence recognition running in time . We improve the running time to . Our algorithm can also be used to compute the longest common subsequence between a compressed text and an uncompressed pattern in time ; the same problem with a compressed pattern is known to be NP-hard. Bibliography: 22 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 358, 2008, pp. 282–300.