Polynomial Time Approximation Scheme for Symmetric Rectilinear Steiner Arborescence Problem

The Symmetric Rectilinear Steiner Arborescence (SRStA) problem is defined as follows: given a set of terminals in the positive quadrant of the plane, connect them using horizontal and vertical lines such that each terminal can be reached from the origin via a y-monotone path and the total length of all the line segments is the minimum possible. Finding an SRStA has applications in VLSI design, in data structures used in some optimization algorithms and in dynamic server problems. In this paper, we provide a polynomial time approximation scheme for the SRStA problem, improving the previous best approximation ratio of 3 for this problem.     

带约束的平行机排序的一个近似算法

讨论有资源约束和有机器准备时间的平行机排序问题,资源约束为每个机器至多可加工k个工件,在极小化makespan的上给出了一个匹配算法,证明其最坏情况最紧界是2-m^-1,并进一步给出了它的两个带参数的最坏情况界。     

素数阶群理论的量词消去及复杂性

本文中我们将研究语言,上素数阶群理论Ｔ的量词消去及相应的复杂性．我们证明理论Ｔ有量词消去性质,并利用该性质给出理论Ｔ判定问题的一个复杂性上界．     

SASEGASA: A New Generic Parallel Evolutionary Algorithm for Achieving Highest Quality Results

This paper presents a new generic Evolutionary Algorithm (EA) for retarding the unwanted effects of premature convergence. This is accomplished by a combination of interacting generic methods. These generalizations of a Genetic Algorithm (GA) are inspired by population genetics and take advantage of the interactions between genetic drift and migration. In this regard a new selection scheme is introduced, which is designed to directedly control genetic drift within the population by advantageous self-adaptive selection pressure steering. Additionally this new selection model enables a quite intuitive heuristics to detect premature convergence. Based upon this newly postulated basic principle the new selection mechanism is combined with the already proposed Segregative Genetic Algorithm (SEGA), an advanced Genetic Algorithm (GA) that introduces parallelism mainly to improve global solution quality. As a whole, a new generic evolutionary algorithm (SASEGASA) is introduced. The performance of the algorithm is evaluated on a set of characteristic benchmark problems. Computational results show that the new method is capable of producing highest quality solutions without any problem-specific additions.     

无严格互补松驰条件的序列线性方程组新算法

该文通过构造特殊形式的有效集来逼近KKT点处的有效集，给出了一个任意初始点下的序列线性方程组新算法，并证明了该算法在没有严格互补松驰条件的情况下具有全局收敛性和一步超线性收敛性。      

一类半线性双曲系统的状态观测问题

本文考虑一类半线性双曲系统的状态观测问题,给出了一个(求解)算法并证明了其在某种相当强的意义上的有效性.     

一类广义非线性混合拟变分包含组

本文引入了一类新的带松弛单调映射和松弛Lipschitz映射的广义非线性混合拟变分包含组 ,构造了求解该类变分包含组的迭代算法 ,证明了该类变分包含组解的存在性以及由本文构造的迭代算法产生的迭代序列的强收敛性 .所得结果推广和改进了大量文献中的最新结果[1 5 ] .     

Fast pattern-matching on indeterminate strings

In a string x on an alphabet Σ, a position i is said to be indeterminate iff x[i] may be any one of a specified subset {λ₁,λ₂,…,λ_j} of Σ, 2j|Σ|. A string x containing indeterminate positions is therefore also said to be indeterminate. Indeterminate strings can arise in DNA and amino acid sequences as well as in cryptological applications and the analysis of musical texts. In this paper we describe fast algorithms for finding all occurrences of a pattern p=p[1..m] in a given text x=x[1..n], where either or both of p and x can be indeterminate. Our algorithms are based on the Sunday variant of the Boyer–Moore pattern-matching algorithm, one of the fastest exact pattern-matching algorithms known. The methodology we describe applies more generally to all variants of Boyer–Moore (such as Horspool's, for example) that depend only on calculation of the δ (“rightmost shift”) array: our method therefore assumes that Σ is indexed (essentially, an integer alphabet), a requirement normally satisfied in practice.     

Computational experience with the Chow—Yorke algorithm

The Chow—Yorke algorithm is a nonsimplicial homotopy type method for computing Brouwer fixed points that is globally convergent. It is efficient and accurate for fixed point problems. L.T. Watson, T.Y. Li, and C.Y. Wang have adapted the method for zero finding problems, the nonlinear complementarity problem, and nonlinear two-point boundary value problems. Here theoretical justification is given for applying the method to some mathematical programming problems, and computational results are presented.This work was partially supported by NSF Grant MCS 7821337.