顶点覆盖约束下的同类机排序算法研究

给定m台同类机和n个工件,其中第j台机器的速度为s_j,第i个工件的加工时间为p_i并且在第j台机器上的负载为p_i/s_j.构造一个顶点赋权无向图G=(V,E;w),其中图G的n个顶点代表这n个工件,顶点权重代表相应工件的加工时间.本文研究顶点覆盖约束下的同类机排序问题.该问题是两个组合最优化问题的组合问题,其目标为首先确定图G的一个顶点覆盖,即图的一个顶点子集,使得图中每一条边都至少存在一个顶点属于该子集;然后把这个子集所代表的相应工件集放到m台同类机上加工,使得最大完工时间最小.该问题是NP-hard的.本文基于分层算法和LSPT算法设计一个■-近似算法,当所有机器的速度都相差不大时,该算法的近似效果较好.     

最小权点覆盖问题的一个近似算法

在点、边赋权的简单图中,关于最小权点覆盖问题,以经典的最短路算法-Dijkstra算法为基础,提出了一个求解该问题的近似算法.首先,在给定的赋权图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法-Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似最小权点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性.     

图的部分控制集问题的修正 Greedy算法

部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小。本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H(K)给出了证明。     

度约束最小生成树的快速算法

本文对带有顶点度约束的最小生成树问题，给出了一种快速近似算法，并在微机上予以实现，经大量试算，效果良好。     

3度图的最小顶点覆盖问题的多项式时间算法

最小顶点覆盖问题是图论和组合数学中经典的NP-Hard问题之一,在实际问题中有着广泛的应用.本文首先给出最小顶点覆盖问题的若干性质,然后根据这些性质设计了3度图最小顶点覆盖问题的一个多项式时间算法,并通过2个实例对算法进行了说明.     

有预算限制的最大多种物资流问题

研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O~(-ε2m2).同时,利用有预算限制的最大多种物资流问题的研究结果,我们也得到了费用最小的最大多种物资流问题的近似算法和算法复杂性.     

求有限集合覆盖的构造方法

在近似算法领域,集合覆盖问题是研究的比较早和比较透彻的问题之一.文中解决与经典SCP不同的另一问题,针对有限集合覆盖的构造,提出一种构造有限集合上的集合覆盖的算法,并且给出了该算法的完备性证明.该算法简单有效,是一种用于构造集合覆盖的规范方法.     

最大割问题和最大平分割问题基于半定规划松弛的近似算法

考虑每条边具有非负权重的无向图, 最大割问题要求将顶点集划分为两个集合使得它们之间的边的权重之和最大. 当最大割问题半定规划松弛的最优解落到二维空间时, Goemans将近似比从0.87856...改进为0.88456. 依赖于半定规划松弛的目标值与总权和的比值的曲线, 此曲线的最低点为0.88456, 当半定规划松弛的目标值与总权和的比值在0.5到0.9044之间时, 利用Gegenbauer多项式舍入技巧, 改进了Zwick的近似比曲线. 进一步, 考虑最大割问题的重要变形------最大平分割问题, 在此问题中增加了划分的两部分的点数相等的要求. 同样考虑了最大平分割问题半定规划松弛的最优解落到二维空间的情形, 并利用前述的Gegenbauer多项式舍入技巧得到0.7091-近似算法.     

带机器准备时间的平行机ordinal排序及近似算法

本文研究带机器准备时间的m台平行机ordinal在线排序问题。讨论了在极小化最大机器完工时间和极小化最大工件完工时间两种目标下的不同下界和相应的在线近似算法。对第一个目标，我们得到了3/2的下界和最坏情况界为2-1/m的近似算法。对第二个目标，我们得到了最坏情况为m的最好近似算法。我们还对一些特殊情况进行了分析。     

基于证据理论的覆盖类决策多粒度粗糙集的下近似约简

知识约简向来是知识发现的重要研究问题之一。该论文研究了基于证据理论的覆盖类决策的多粒度粗糙集的约简方法。首先构造了覆盖类决策多粒度粗糙集的信任结构,然后利用该信任结构中的信任函数和似然函数刻画了覆盖类决策多粒度粗糙集的约简特征,再者引入了基于信任函数的覆盖重要度的概念,并给出了求解覆盖约简的近似算法。最后用实例说明该算法的合理性和有效性。     

Essential extensions, excellent extensions and finitely presented dimension

In Section 1 of this paper, we investigate the finitely presented dimension of an essential extension for a module, and obtain results concerning an essential extension of a torsion-free module. We partially answer the question: When is an essential extension of a finitely presented module (an almost finitely presented module) also finitely presented (almost finitely presented)? In Section 2, we study theC-excellent extensions and the finitely presented dimensions. We obtain some results on the homological dimensions of matrix rings and group rings.     

Iterative and non-iterative methods for non-linear Volterra integro-differential equations

Iterative and non-iterative methods for the solution of nonlinear Volterra integro-differential equations are presented and their local convergence is proved. The iterative methods provide a sequence solution and make use of fixed-point theory, whereas the non-iterative ones result in series solutions and also make use of fixed-point principles. By means of integration by parts and use of certain integral identities, it is shown that the initial conditions that appear in the iterative methods presented here can be eliminated and the resulting iterative technique is identical to the variational iteration method which is derived here without making any use at all of Lagrange multipliers and constrained variations. It is also shown that the formulation presented here can be applied to initial-value problems in ordinary differential, Volterra’s integral and integro-differential, pantograph, and nonlinear and linear algebraic equations. A technique for improving/accelerating the convergence of the iterative methods presented here is also presented and results in a Lipschitz constant that may be varied as the iteration progresses. It is shown that this acceleration technique is related to preconditioning methods for the solution of linear algebraic equations. It is also argued that the non-iterative methods presented in this paper may not competitive with iterative ones because of possible cancellation errors, if implemented numerically. An analytical continuation procedure based on dividing the interval of integration into disjoint subintervals is also presented and its limitations are discussed.     

A theory for nonlinear soft webs

In this paper, a fundamental theory for deformable webs not resisting any compressive membrane forces is developed through a direct derivation on the deformed configuration. In order to better describe the deformable webs, the classification of deformable webs is presented. A theory for the non-continuum elastic network webs consisting of many deformable cables is presented from the deformable cable theory, and then a theory for fabric deformable webs without relative sliding is developed as well. Finally, a nonlinear theory for continuous deformable webs is presented on the deformed configuration. The local criteria for the existence of such deformable webs are presented through the definitions, and such criteria are very significant for the wrinkling stability of the deformable webs. A deformable web possessing the local wrinkling is an unsolved problem in numerical computations. The theory for fabric webs with relative motions needs to be further developed. Herein the fundamental theory for deformable webs is presented only, and numerical examples will be presented in sequel. Such a theory of deformable webs can be applied to textile or other soft materials and bio-membranes.     

本刊英文版2014年57卷第9期摘要

On variations of m, n-simply presented abelian p-groups     

On a class of Jacobi-like procedures for diagonalising arbitrary real matrices

Summary A new class of elementary matrices is presented which are convenient in Jacobi-like diagonalisation methods for arbitrary real matrices. It is shown that the presented transformations possess the normreducing property and that they produce an ultimate quadratic convergence even in the case of complex eigenvalues. Finally, a quadratically convergent Jacobi-like algorithm for real matrices with complex eigenvalues is presented.     

An efficient third-moment saddlepoint approximation for probabilistic uncertainty analysis and reliability evaluation of structures

This paper presents an efficient third-moment saddlepoint approximation approach for probabilistic uncertainty analysis and reliability evaluation of random structures. By constructing a concise cumulant generating function (CGF) for the state variable according to its first three statistical moments, approximate probability density function and cumulative distribution function of the state variable, which may possess any types of distribution, are obtained analytically by using saddlepoint approximation technique. A convenient generalized procedure for structural reliability analysis is then presented. In the procedure, the simplicity of general moment matching method and the accuracy of saddlepoint approximation technique are integrated effectively. The main difference of the presented method from existing moment methods is that the presented method may provide more detailed information about the distribution of the state variable. The main difference of the presented method from existing saddlepoint approximation techniques is that it does not strictly require the existence of the CGFs of input random variables. With the advantages, the presented method is more convenient and can be used for reliability evaluation of uncertain structures where the concrete probability distributions of input random variables are known or unknown. It is illustrated and examined by five representative examples that the presented method is effective and feasible.     

求解界约束优化的一种新的非单调谱投影梯度法

本文给出求解界约束优化问题的一种新的非单调谱投影梯度算法. 该算法是将谱投影梯度算法与Zhang and Hager [SIAM Journal on Optimization,2004,4（4）：1043-1056]提出的非单调线搜索结合得到的方法. 在合理的假设条件下,证明了算法的全局收敛性.数值实验结果表明,与已有的界约束优化问题的谱投影梯度法比较,利用本文给出的算法求解界约束优化问题是有竞争力的.     

On Presentations of Bruck–Reilly Extensions

We first consider the class of monoids in which every left invertible element is also right invertible, and prove that if a monoid belonging to this class admits a finitely presented Bruck–Reilly extension then it is finitely generated. This allow us to obtain necessary and sufficient conditions for the Bruck–Reilly extensions of this class of monoids to be finitely presented. We then prove that thes 𝒟-classes of a Bruck–Reilly extension of a Clifford monoid are Bruck–Reilly extensions of groups. This yields another necessary and sufficient condition for these Bruck–Reilly extensions to be finitely generated and presented. Finally, we show that a Bruck–Reilly extension of a Clifford monoid is finitely presented as an inverse monoid if and only if it is finitely presented as a monoid, and that this property cannot be generalized to Bruck–Reilly extensions of arbitrary inverse monoids.     

An Algorithmic Approach to Discrete Time Non-homogeneous Backward Semi-Markov Reward Processes with an Application to Disability Insurance

In this paper semi-Markov reward models are presented. Higher moments of the reward process is presented for the first time applied to in time non-homogeneous semi-Markov insurance problems. Also an example is presented based on real disability data. Different algorithmic approaches to solve the problem is described. This work is partly supported by the Knowledge Foundation and Sparbankens Stiftelse Nya. The authors would like to thank the anonymous referee.     

A tri-Hamiltonian formulation of a new soliton hierarchy associated with so(3,R)

A third Hamiltonian operator is presented for a new hierarchy of bi-Hamiltonian soliton equations, thereby showing that this hierarchy is tri-Hamiltonian. Additionally, an inverse hierarchy of common commuting symmetries is also presented.