A dynamic programming solution to a generalized LCS problem

In this paper, we consider a generalized longest common subsequence problem, the string-excluding constrained LCS problem. For the two input sequences X and Y of lengths n and m, and a constraint string P of length r, the problem is to find a common subsequence Z of X and Y excluding P as a substring and the length of Z is maximized. The problem and its solution were first proposed by Chen and Chao (2011) [1], but we found that their algorithm cannot solve the problem correctly. A new dynamic programming solution for the STR-EC-LCS problem is then presented in this paper. The correctness of the new algorithm is proved. The time complexity of the new algorithm is $O(nmr)$.     

The indexing for one-dimensional proportionally-scaled strings

Related problems of scaled matching and indexing, which aim to determine all positions in a text T that a pattern P occurs in its scaled form, are considered important because of their applications to computer vision. However, previous results only focus on enlarged patterns, and do not allow shrunk patterns since they may disappear. In this paper, we give the definition and an efficient indexing algorithm for proportionally-scaled patterns that can be visually enlarged or shrunk. The proposed indexing algorithm takes O(|T|) time in its preprocessing phase, and achieves time in its answering phase, where |T|, |P|, Up, and m denote the length of T, the length of P, the number of reported positions, and the length of T under run-length representation, respectively.     

基于Gabor小波和局部线性嵌入的人脸识别

提出了一种新的人脸识别算法。该算法采用Gabor小波和一种新颖的方式来提取人脸特征,利用局部线性嵌入（Locally Linear Embedding,LLE）算法来实现数据的非线性降维处理,最后训练基于欧式距离的最近邻分类器进行分类判决。在ORL人脸库中与PCA方法、Gabor小波+PCA方法和直接的LLE算法进行了实验比较,实验结果表明,提出的Gabor小波+LLE的方法具有更优的性能。     

De‐embedding of filters in multiplexers via rational approximation and interpolation

In this article, we present a method to recover electrical parameters of filters embedded in a multiplexer for which scattering measurements are given. Unlike other approaches proposed for this problem, this method does not require a priori knowledge of the scattering parameters of the junction. This feature renders the procedure well suited for tuning purposes or for fault diagnosis. Technically, the algorithm starts with a rational approximation step, to derive a rational representation of certain scattering parameters of the multiplexer. This representation is then used in a second step to identify an electrical model of each filter. This second step relies on a rational interpolation technique used to extract the filter's responses. © 2015 Wiley Periodicals, Inc. Int J RF and Microwave CAE 25:647–654, 2015.     

The hardness of approximation: Gap location

We refine the complexity analysis of approximation problems by relating it to a new parameter calledgap location. Many of the results obtained so far for approximations yield satisfactory analysis with respect to this refined parameter, but some known results (e.g.,max-k-colorability, max 3-dimensional matching andmax not-all-equal 3sat) fall short of doing so. As a second contribution, our work fills the gap in these cases by presenting new reductions.Next, we present definitions and hardness results of new approximation versions of some NP-complete optimization problems. The problems we treat arevertex cover (for which we define a different optimization problem from the one treated in Papadimitriou & Yannakakis 1991),k-edge coloring, andset splitting.     

Optimal parallel detection of squares in strings

A stringw isprimitive if it is not a power of another string (i.e., writingw =v ^k impliesk = 1. Conversely,w is asquare ifw =vv, withv a primitive string. A stringx issquare-free if it has no nonempty substring of the formww. It is shown that the square-freedom of a string ofn symbols over an arbitrary alphabet can be tested by a CRCW PRAM withn processors inO(logn) time and linear auxiliary space. If the cardinality of the input alphabet is bounded by a constant independent of the input size, then the number of processors can be reduced ton/logn without affecting the time complexity of this strategy. The fastest sequential algorithms solve this problemO(n logn) orO(n) time, depending on whether the cardinality of the input alphabet is unbounded or bounded, and either performance is known to be optimal within its class. More elaborate constructions lead to a CRCW PRAM algorithm for detecting, within the samen-processors bounds, all positioned squares inx in timeO(logn) and using linear auxiliary space. The fastest sequential algorithms solve this problem inO(n logn) time, and such a performance is known to be optimal.This research was supported, through the Leonardo Fibonacci Institute, by the Istituto Trentino di Cultura, Trento, Italy. Additional support was provided by the French and Italian Ministries of Education, by the National Research Council of Italy, by the British Research Council Grant SERC-E76797, by NSF Grant CCR-89-00305, by NIH Library of Medicine Grant ROI LM05118, by AFOSR Grant 90-0107, and by NATO Grant CRG900293.     

Parameterized approximation of dominating set problems

A problem open for many years is whether there is an FPT algorithm that given a graph G and parameter k, either: (1) determines that G has no k-Dominating Set, or (2) produces a dominating set of size at most g(k), where g(k) is some fixed function of k. Such an outcome is termed an FPT approximation algorithm. We describe some results that begin to provide some answers. We show that there is no such FPT algorithm for g(k) of the form k+c (where c is a fixed constant, termed an additive FPT approximation), unless FPT=W[2]. We answer the analogous problem completely for the related Independent Dominating Set (IDS) problem, showing that IDS does not admit an FPT approximation algorithm, for any g(k), unless FPT=W[2].     

Embedding meshes into locally twisted cubes

As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, mesh embeddings in locally twisted cubes are studied. Let LTQ_n(V, E) denote the n-dimensional locally twisted cube. We present three major results in this paper: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded in LTQ_n with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded in LTQ_n with dilation 1 and expansion 2. (3) For any integer n ? 3, a 4  × (2ⁿ⁻² − 1) mesh can be embedded in LTQ_n with dilation 2. The first two results are optimal in the sense that the dilations of all embeddings are 1. The embedding of the 2 × 2ⁿ⁻¹ mesh is also optimal in terms of expansion. We also present the analysis of 2p × 2q mesh embedding in locally twisted cubes.     

Global and local choice of the number of nearest neighbors in locally linear embedding

The crux in the locally linear embedding algorithm is the selection of the number of nearest neighbors k. Some previous techniques have been developed for finding this parameter based on embedding quality measures. Nevertheless, they do not achieve suitable results when they are tested on several kind of manifolds. In this work is presented a new method for automatically computing the number of neighbors by means of analyzing global and local properties of the embedding results. Besides, it is also proposed a second strategy for choosing the parameter k, on manifolds where the density and the intrinsic dimensionality of the neighborhoods are changeful. The first proposed technique, called preservation neighborhood error, calculates a unique value of k for the whole manifold. Moreover, the second method, named local neighborhood selection, computes a suitable number of neighbors for each sample point in the manifold. The methodologies were tested on artificial and real-world datasets which allow us to visually confirm the quality of the embedding. According to the results our methods aim to find suitable values of k and appropriated embeddings.     

基于监督局部线性嵌入特征提取的高光谱图像分类

高光谱图像的数据维数高、数据量大、数据间高度冗余等特点给图像分类带来困难,为进行有效降维、提高分类精度,提出了一种监督局部线性嵌入(SLLE)非线性流形学习特征提取方法。SLLE算法根据数据先验类标签信息所给出的新距离寻找数据点的k最近邻(NN),新距离使得类内距离小于类间距离,这使得SLLE算法更有利于分类。高光谱图像数据和UCI数据的分类结果表明了该方法的有效性。     

Constant ratio fixed-parameter approximation of the edge multicut problem

The input of the Edge Multicut problem consists of an undirected graph G and pairs of terminals {s₁,t₁},…,{sm,tm}; the task is to remove a minimum set of edges such that si and ti are disconnected for every 1?i?m. The parameterized complexity of the problem, parameterized by the maximum number k of edges that are allowed to be removed, is currently open. The main result of the paper is a parameterized 2-approximation algorithm: in time f(k)⋅nO(1), we can either find a solution of size 2k or correctly conclude that there is no solution of size k.The proposed algorithm is based on a transformation of the Edge Multicut problem into a variant of the parameterized Max-2SAT problem, where the parameter is related to the number of clauses that are not satisfied. It follows from previous results that the latter problem can be 2-approximated in a fixed-parameter time; on the other hand, we show here that it is W[1]-hard. Thus the additional contribution of the present paper is introducing the first natural W[1]-hard problem that is constant-ratio fixed-parameter approximable.     

Multi‐organization scheduling approximation algorithms

In this paper we consider the problem of scheduling on computing platforms composed of several independent organizations, known as the Multi‐Organization Scheduling Problem (MOSP). Each organization provides both resources and jobs and follows its own objectives. We are interested in the best way to minimize the makespan on the entire platform when the organizations behave in a selfish way. We study the complexity of the MOSP problem with two different local objectives—makespan and average completion time—and show that MOSP is strongly NP‐Hard in both cases. We formally define a selfishness notion, by means of restrictions on the schedules. We prove that selfish behavior imposes a lower bound of 2 on the approximation ratio for the global makespan. We present various approximation algorithms of ratio 2 which validate selfishness restrictions. These algorithms are experimentally evaluated through simulation, exhibiting good average performances and presenting good fairness to organizations' local objectives. Copyright © 2011 John Wiley & Sons, Ltd.     

Linear stochastic approximation driven by slowly varying Markov chains

We study a linear stochastic approximation algorithm that arises in the context of reinforcement learning. The algorithm employs a decreasing step-size, and is driven by Markov noise with time-varying statistics. We show that under suitable conditions, the algorithm can track the changes in the statistics of the Markov noise, as long as these changes are slower than the rate at which the step-size of the algorithm goes to zero.     

A polynomial time approximation scheme for embedding a directed hypergraph on a ring

We study the problem of embedding a directed hypergraph on a ring that has applications in optical network communications. The undirected version (MCHEC) has been extensively studied. It was shown that the undirect version was NP-complete. A polynomial time approximation scheme (PTAS) for the undirected version has been developed. In this paper, we design a polynomial time approximation scheme for the directed version.     

On different approximation criteria for subset product problems

We study and compare three different approximation criteria for a class of problems with product objective function. We also show that a dominance rule is a necessary and sufficient condition for the approximability of the same class of problems.     

基于监督局部线性嵌入的中药材分类鉴别研究*

电子鼻所采集的中药材气味信息往往具有高维性和非线性。针对气味信息的这种特性,提出一种基于监督局部线性嵌入(SLLE)和线性判别分析(LDA)的气味数据分析方法。首先利用SLLE对所采集的高维非线性气味信息进行降维,目的是提取出气味数据内在的低维流行特征,并增大类别间的辨别信息。然后,在低维空间中,利用LDA进行特征分类判别。通过实验,分别将该方法与单独使用SLLE方法及PCA LDA方法进行对比分析,结果表明,该方法可以很好地对五种不同种类的中药材及三种不同产地的何首乌进行分类鉴别,其个体识别率和整体识别率均可达到100%,为使用电子鼻对中药材进行分类鉴别提供了一种行之有效的方法。     

Reinforcement learning via approximation of the Q-function

Relational reinforcement learning (RRL) combines traditional reinforcement learning (RL) with a strong emphasis on a relational (rather than attribute-value) representation. Earlier work used RRL on a learning version of the classic Blocks World planning problem (a version where the learner does not know what the result of taking an action will be) and the Tetris game. Learning results based on the structure of training examples were obtained, such as learning in a mixed 3–5 block environment and being able to perform in a 3 or 10 block environment. Here, we instead take a function approximation approach to RL for the Blocks World problem. We obtain similar learning accuracies, with better running times, allowing us to consider much larger problem sizes. For instance, we can train on 15 blocks and then perform well on worlds with 100–800 blocks–using less running time than the relational method required to perform well for 3–10 blocks.     

Smooth surface approximation to serial cross-sections

The reconstruction of the surface model of an object from 2D cross-sections plays an important role in many applications. In this paper, we present a method for surface approximation to a given set of 2D contours. The resulting surface is represented by a bicubic closed B-spline surface with C² continuity. The method performs the skinning of intermediate contour curves represented by cubic B-spline curves on a common knot vector, each of which is fitted to its contour points within a given accuracy. In order to acquire more compact representation for the surface, the method includes an algorithm for reducing the number of knots in the common knot vector. The proposed method provides a smooth and accurate surface model, yet realizes efficient data reduction. Some experimental results are given using synthetic and MRI data.     

Polynomial approximation to clothoids via s-power series

Given an arbitrary segment of a clothoid over a finite interval, we propose a novel method for generating a polynomial approximation, based on employing s-power series, the two-point analogue of Taylor expansions. Truncating at the kth term the s-power series furnishes the order-k Hermite interpolant, i.e. the degree-(2k+1) polynomial curve that reproduces up to the kth derivative of the original curve at the endpoints of a given interval. By piecing these approximations we obtain a Hermitian spline that exhibits C^k continuity at the joints and enjoys almost arc-length parameterization. This is a more suitable alternative than the truncated Taylor series or the blending of Taylor expansions advocated by Wang et al. [Computer-Aided Design 33 (2001) 1049] in a recent article.     

Surface approximation via sparse representation and parameterization optimization

Surface approximation with smooth functions suffers the problems of choosing the basis functions and representing non-smooth features. In this work, we introduce a sparse representation for surfaces with a set of redundant basis functions, which efficiently overcomes the overfitting artifacts. Moreover, we propose an approach of parameterization transformation, which makes the possibility to represent non-smooth features by the composition of a smooth function and a non-smooth domain optimization. We couple the sparse representation and the parameterization transformation in a global optimization to respect sharp features with smooth polynomial basis functions. Our approach is capable for approximating a wide range of surfaces with different level of sharp features. Experimental results have shown the feasibility and applicability of our proposed method in various applications.