Parameterized matching with mismatches

The problem of approximate parameterized string searching consists of finding, for a given text t=t₁t₂…t_n and pattern p=p₁p₂…p_m over respective alphabets Σ_t and Σ_p, the injection π_i from Σ_p to Σ_t maximizing the number of matches between π_i(p) and t_it_i+1…t_i+m−1 (i=1,2,…,n−m+1). We examine the special case where both strings are run-length encoded, and further restrict to the case where one of the alphabets is binary. For this case, we give a construction working in time O(n+(r_p×r_t)α(r_t)log(r_t)), where r_p and r_t denote the number of runs in the corresponding encodings for y and x, respectively, and α is the inverse of the Ackermann's function.     

A new trust region method with adaptive radius

In this paper we develop a new trust region method with adaptive radius for unconstrained optimization problems. The new method can adjust the trust region radius automatically at each iteration and possibly reduces the number of solving subproblems. We investigate the global convergence and convergence rate of this new method under some mild conditions. Theoretical analysis and numerical results show that the new adaptive trust region radius is available and reasonable and the resultant trust region method is efficient in solving practical optimization problems. The work was supported in part by NSF grant CNS-0521142, USA.     

An effective architecture for learning and evolving flexible job-shop schedules

In recent years, the interaction between evolution and learning has received much attention from the research community. Some recent studies on machine learning have shown that it can significantly improve the efficiency of problem solving when using evolutionary algorithms. This paper proposes an architecture for learning and evolving of Flexible Job-Shop schedules called LEarnable Genetic Architecture (LEGA). LEGA provides an effective integration between evolution and learning within a random search process. Unlike the canonical evolution algorithm, where random elitist selection and mutational genetics are assumed; through LEGA, the knowledge extracted from previous generation by its schemata learning module is used to influence the diversity and quality of offsprings. In addition, the architecture specifies a population generator module that generates the initial population of schedules and also trains the schemata learning module. A large range of benchmark data taken from literature and some generated by ourselves are used to analyze the efficacy of LEGA. Experimental results indicate that an instantiation of LEGA called GENACE outperforms current approaches using canonical EAs in computational time and quality of schedules.     

Technique for gray-scale visual light and infrared image fusion based on non-subsampled shearlet transform

A novel image fusion technique based on NSST (non-subsampled shearlet transform) is presented, aiming at resolving the fusion problem of spatially gray-scale visual light and infrared images. NSST, as a new member of MGA (multi-scale geometric analysis) tools, possesses not only flexible direction features and optimal shift-invariance, but much better fusion performance and lower computational costs compared with several current popular MGA tools such as NSCT (non-subsampled contourlet transform). We specifically propose new rules for the fusion of low and high frequency sub-band coefficients of source images in the second step of the NSST-based image fusion algorithm. First, the source images are decomposed into different scales and directions using NSST. Then, the model of region average energy (RAE) is proposed and adopted to fuse the low frequency sub-band coefficients of the gray-scale visual light and infrared images. Third, the model of local directional contrast (LDC) is given and utilized to fuse the corresponding high frequency sub-band coefficients. Finally, the final fused image is obtained by using inverse NSST to all fused sub-images. In order to verify the effectiveness of the proposed technique, several current popular ones are compared over three different publicly available image sets using four evaluation metrics, and the experimental results demonstrate that the proposed technique performs better in both subjective and objective qualities.     

An improved lower bound for the expected number of real zeros of a random algebraic polynomials

In this note we estimate the lower bound of the average number of real zeros of a random algebraic polynomials when the random coefficients are standard normal random variables     

Inverted Region in Intermolecular Electronic Energy Transfer

A critique of some recent publications (concerning the so-called inverted region in exchange-induced electronic energy transfer) is presented. It is first pointed out that the phenomena reported therein have in fact been known for nearly two decades; next, a derivation of the expression (used in the aforementioned communications) for k _EnT, the transfer rate constant, is presented; finally, it is stressed that this formula cannot provide reliable quantitative predictions.     

k-Abelian pattern matching

Two words are called k-abelian equivalent, if they share the same multiplicities for all factors of length at most k. We present an optimal linear time algorithm for identifying all occurrences of factors in a text that are k-abelian equivalent to some pattern P. Moreover, an optimal algorithm for finding the largest k for which two words are k-abelian equivalent is given. Solutions for online versions of the k-abelian pattern matching problem are also proposed.     

Polynomial-time perfect matchings in dense hypergraphs

Let H be a k-graph on n   vertices, with minimum codegree at least n/k+cn$n/k+cn$ for some fixed c>0$c>0$. In this paper we construct a polynomial-time algorithm which finds either a perfect matching in H   or a certificate that none exists. This essentially solves a problem of Karpiński, Ruciński and Szymańska; Szymańska previously showed that this problem is NP-hard for a minimum codegree of n/k−cn$n/k-cn$. Our algorithm relies on a theoretical result of independent interest, in which we characterise any such hypergraph with no perfect matching using a family of lattice-based constructions.     

Numerical Optimal Harvesting for an Age-Dependent Prey-Predator System

In this article, we develop a numerical study of an optimal harvesting problem for age-dependent prey-predator system. Here, the rates of growth and decay as well as the interaction effect between species are assumed to be depending on age, time and space. Existence, uniqueness, and necessary conditions for the optimal control are assured in case of a small final time T. The discrete parabolic nonlinear dynamical systems are obtained by using a finite difference semi-implicit scheme. Then a numerical algorithm is developed to approximate the optimal harvesting effort and the optimal harvest. Results of the numerical tests are given.     

Constructing arithmetic subgroups of unipotent groups

Let G be a unipotent algebraic subgroup of some defined over . We describe an algorithm for finding a finite set of generators of the subgroup . This is based on a new proof of the result (in more general form due to Borel and Harish-Chandra) that such a finite generating set exists.