Quadratic-time algorithm for a string constrained LCS problem

The problem of finding a longest common subsequence of two main sequences with some constraint that must be a substring of the result (STR-IC-LCS) was formulated recently. It is a variant of the constrained longest common subsequence problem. As the known algorithms for the STR-IC-LCS problem are cubic-time, the presented quadratic-time algorithm is significantly faster.     

An almost-linear time and linear space algorithm for the longest common subsequence problem

There are two general approaches to the longest common subsequence problem. The dynamic programming approach takes quadratic time but linear space, while the nondynamic-programming approach takes less time but more space. We propose a new implementation of the latter approach which seems to get the best for both time and space for the DNA application.     

异构机群系统上并行计算双序列的最长公共子序列*

针对处理机节点具有不同计算速度、不同通信能力的情况,考虑计算和通信启动开销,给定处理机分配顺序,基于可分负载理论,提出一种存储受限异构机群系统的序列串最优分配线性规划模型,给出相应的序列串最优分配方法。实验结果表明,基于最优序列串分配方法的双序列最长公共子序列并行算法优于平均分配序列串算法,获得了较好的加速,并具有良好的可扩展性。     

A linear algorithm for the all-bidirectional-edges problem on planar graphs

The all-bidirectional-edges problem is to find an edge-labeling of an undirected networkG=(V, E), with a source and a sink, such that an edgee=uv inE is labeled u, v or u, u (or both) depending on the existence of a (simple) path from the source to the sink traversinge, that visits the verticesu andv in the orderu, v orv, u respectively. The best-known algorithm for this problem requiresO(¦V¦·¦E¦) time [5]. We show that the problem is solvable optimally on a planar graph.     

The set-set LCS problem

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which both of the input strings consists of sets of symbols which may be permuted.     

The set-set LCS problem

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which both of the input strings consists of sets of symbols which may be permuted.     

The set LCS problem

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which one of the two input strings contains sets of symbols which may be permuted. This problem arises from a music application.     

The set LCS problem

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which one of the two input strings contains sets of symbols which may be permuted. This problem arises from a music application.     

A negative dual rectangle cancellation algorithm for the linear assignment problem

In this paper, we consider three alternative primal models and their corresponding alternative dual models for the linear assignment problem. We then define the concept of Negative Dual Rectangle (NDR) and suggest an algorithm that solves two of these dual problems by repeatedly finding and cancelling NDRs until it yields an optimal solution to the assignment problem. The algorithm is simple, flexible, efficient, and unified. We also introduce the notion of partial zero cover as an interpretation of an NDR. We then introduce some heuristic methods for finding NDRs. We also state and prove a lemma to establish the optimal use of an NDR. Furthermore, we show that on a new class of benchmark instances that is introduced in this paper the running time of our algorithm is highly superior to a well-known pure shortest path algorithm.     

A global optimization algorithm for solving the bi-level linear fractional programming problem

In this paper, we obtain the solution to bi-level linear fractional programming problem (BLFP) by means of an optimization algorithm based on the duality gap of the lower level problem. In our algorithm, the bi-level linear fractional programming problem is transformed into an equivalent single level programming problem by forcing the dual gap of the lower level problem to zero. Then, by obtaining all vertices of a polyhedron, the single level programming problem can be converted into a series of linear fractional programming problems. Finally, the performance of the proposed algorithm is tested on a set of examples taken from the literature.     

A problem space genetic algorithm in multiobjective optimization

In this study, a problem space genetic algorithm (PSGA) is used to solve bicriteria tool management and scheduling problems simultaneously in flexible manufacturing systems. The PSGA is used to generate approximately efficient solutions minimizing both the manufacturing cost and total weighted tardiness. This is the first implementation of PSGA to solve a multiobjective optimization problem (MOP). In multiobjective search, the key issues are guiding the search towards the global Pareto-optimal set and maintaining diversity. A new fitness assignment method, which is used in PSGA, is proposed to find a well-diversified, uniformly distributed set of solutions that are close to the global Pareto set. The proposed fitness assignment method is a combination of a nondominated sorting based method which is most commonly used in multiobjective optimization literature and aggregation of objectives method which is popular in the operations research literature. The quality of the Pareto-optimal set is evaluated by using the performance measures developed for multiobjective optimization problems.     

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)$.     

求解线性规划问题的光滑型牛顿算法

对线性规划的最优性条件,给出一个扩展系统,设计一个连续化的光滑型算法求解该系统。所设计的算法的全局收敛性不需要添加任何假设条件。在每一个迭代点处,只需要解一个线性方程组和做一次线性搜索,比现有求解线性规划问题的连续化方法具有更好的收敛性质。     

Solution algorithm for an optimistic linear Stackelberg problem

The optimistic Stackelberg problem is a bilevel programming problem where the constraints in the lower level problem are parameter independent. For linear problems of that type, algorithms for computing local and global optimal solutions are suggested. Their convergence is shown. In the last part, problems with perturbed right-hand side of the lower level constraints are considered, and the behavior of optimal solutions and of the optimal function value is investigated.     

基因序列相似程度的LCS算法研究

首先重新审视了采用穷举法求解LCS问题的困难,以及对应的优点;随后针对穷举法的优点进行了两类优化;最后给出了算法实现的图示以及算法的结论。通过实验证明,算法的效率较传统的动态规划的LCS算法有了很大的提升。     

The hybrid algorithm for solving the three-level linear programming problem

Several algorithms have been developed to solve two-level programming problem during the past years. In this paper, we will develop an algorithm for solving three-level programming problem. The hybrid algorithm is coded and used to test a group of problems. Computational experience and comparisons will be presented.