复合并行机F''''2|m1≥2,m2=1|Cmax排序问题的归并算法研究

在文献[1]中,已经证明了排序问题F2|m1≥2,m2=1|Cmax是NP完全问题,没有好算法.本文提出了复合并行机F'2|m1≥2,m2=1|Cmax排序问题的一个启发式算法--归并算法,并证明了该算法在最坏情况下的性能比(Performance Ratio)是2m-1/m,且优于文献[2]中算法.     

KIM算法的最优性

研究工件的就绪时间可以不相同、但是与交货期有＂一致性＂关系的误工问题.1978年Kise,Ibaraki,Mine提出算法（简称为KIM算法）,证明他们提出的KIM算法可以得到这个误工问题的最优解.最近李杉林、陈志龙、唐国春用反例指出Kise,Ibaraki,Mine证明最优性时提出的引理2是错误的,并用新的方法证明KIM算法的最优性.越民义则给出一个非常简洁的证明.本文分析引理2的错误所在,给出修改后的引理2’,由此似乎应该相应修改KIM算法,然而我们证明原来的KIM算法仍然可以得到最优解.     

广义超立方体网络的寻径算法

利用H amm ing距离概念,在广义超立方体中的点对之间提出两个基于H amm ing距离的确定性寻径算法—算法1、算法2,分析了这两种算法的特点.为了克服确定性寻径算法易出现的通道拥挤现象,文中提出了一种自适应算法—算法3.     

分布式L_(1/2)正则化

研究数据集被分割并存储于不同处理器时的特征提取和变量选择问题,其中处理器通过某种网络结构相互连接.提出分布式L_(1/2)正则化方法,基于ADMM算法给出分布式L_(1/2)正则化算法,证明了算法的收敛性.算法通过相邻处理器之间完成信息交互,其变量选择结果与数据集不分割时利用L_(1/2)正则化相同.实验表明,所提出的新算法有效、实用,适合于分布式存储数据处理.     

N维2带小波紧框架的构造

给出了$m$个函数生成$N$维2带小波紧框架的充分条件和$N$维2带小波紧框架的显式构造算法, 讨论了小波紧框架的分解算法与重构算法. 提出的构造方法很有普遍性, 容易推广到$N(N\geq2)$维$M(M\geq 2)$带小波紧框架的情形,也可以得到类似的小波紧框架的分解算法与重构算法.     

不重叠型Schwarz交替法的加速收敛

Matsokin与Nepomnyaschikh所提出的不重叠型S交替法的算法中不含有松弛因子，我们知道它有与h无关的几何收敛速度，但由于不含算法参数，该算法不能根据具体的情况加速收敛，本文提出加速收敛算法，我们在原算法的基础上引入两个松弛因子θ2，θ2并证明了除了例外均可实现加速收敛，θ1=θ^-1，θ2=θ^-2是满足均衡条件的最佳松弛因子，最后的算例表明该加速算法的有效性。     

求解半线性抛物问题的两种二重网格算法

用线性方法对半线性抛物问题进行求解。方法依赖粗、细二重网格,针对粗解在细网格上的修正提出了两种算法,算法1是乘积倍的增长精度而算法2是平方倍的增长精度,而且重复算法1、2的最后几步可以任意阶地逼近细网格上的非线性解。数值算例验证了算法的可行性和有效性。     

极小化总加权完工时间的Dial-a-Ride问题的在线随机算法

讨论一般度量空间上带单服务器的极小化总加权完工时间在线Dial-a-Ride问题.通过应用贪婪区间的技巧,提出了一个一般在线随机算法.根据这个算法,对于容量为1或者任意容量的一般度量空间上的在线Dial-a-Ride问题能得到一个竞争比为(2+√2)/ln(1+√2)的在线随机算法,这个算法不仅具有当前最好的竞争比,而且也改进了Krumke等人的结果.     

一种用于分布式同步的令牌算法

本文提出了一种称为令牌算法的分布式同步算法.按此算法每达成一次互斥协议仅需发送信件N封,此处N为网络中结点的个数,而采用其它的几种分布式同步算法时需发送2N或更多的信件.本文还讨论了分布式同步算法的好环标准.按本文提出的标准,令牌算法是最佳的分布式同步算法.     

两台机器超载实时系统的On-line算法

对超载实时系统的On—line算法中的SR算法作了修改，提出了NSR算法，并证明NSR算法的竞争比至少为2／5，因而它比SR算法更为优异．     

A hybrid heuristic algorithm for the 2D variable-sized bin packing problem

In this paper, we consider the two-dimensional variable-sized bin packing problem (2DVSBPP) with guillotine constraint. 2DVSBPP is a well-known NP-hard optimization problem which has several real applications. A mixed bin packing algorithm (MixPacking) which combines a heuristic packing algorithm with the Best Fit algorithm is proposed to solve the single bin problem, and then a backtracking algorithm which embeds MixPacking is developed to solve the 2DVSBPP. A hybrid heuristic algorithm based on iterative simulated annealing and binary search (named HHA) is then developed to further improve the results of our Backtracking algorithm. Computational experiments on the benchmark instances for 2DVSBPP show that HHA has achieved good results and outperforms existing algorithms.     

Computing the complete CS decomposition

An algorithm for computing the complete CS decomposition of a partitioned unitary matrix is developed. Although the existence of the CS decomposition (CSD) has been recognized since 1977, prior algorithms compute only a reduced version. This reduced version, which might be called a 2-by-1 CSD, is equivalent to two simultaneous singular value decompositions. The algorithm presented in this article computes the complete 2-by-2 CSD, which requires the simultaneous diagonalization of all four blocks of a unitary matrix partitioned into a 2-by-2 block structure. The algorithm appears to be the only fully specified algorithm available. The computation occurs in two phases. In the first phase, the unitary matrix is reduced to bidiagonal block form, as described by Sutton and Edelman. In the second phase, the blocks are simultaneously diagonalized using techniques from bidiagonal SVD algorithms of Golub, Kahan, Reinsch, and Demmel. The algorithm has a number of desirable numerical features.      

A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O(n~(1/2)L) iteration complexity which is the best result for convex quadratic programming so far.     

Sequential Systems of Linear Equations Algorithm for Nonlinear Optimization Problems with General Constraints

In Ref. 1, a new superlinearly convergent algorithm of sequential systems of linear equations (SSLE) for nonlinear optimization problems with inequality constraints was proposed. At each iteration, this new algorithm only needs to solve four systems of linear equations having the same coefficient matrix, which is much less than the amount of computation required for existing SQP algorithms. Moreover, unlike the quadratic programming subproblems of the SQP algorithms (which may not have a solution), the subproblems of the SSLE algorithm are always solvable. In Ref. 2, it is shown that the new algorithm can also be used to deal with nonlinear optimization problems having both equality and inequality constraints, by solving an auxiliary problem. But the algorithm of Ref. 2 has to perform a pivoting operation to adjust the penalty parameter per iteration. In this paper, we improve the work of Ref. 2 and present a new algorithm of sequential systems of linear equations for general nonlinear optimization problems. This new algorithm preserves the advantages of the SSLE algorithms, while at the same time overcoming the aforementioned shortcomings. Some numerical results are also reported.     

Graph Sparsification by Universal Greedy Algorithms

Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications, such as simplification of social networks, least squares problems, and numerical solution of symmetric positive definite linear systems. In this paper, inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit (OMP), we introduce a deterministic, greedy edge selection algorithm, which is called the universal greedy approach (UGA) for the graph sparsification problem. For a general spectral sparsification problem, e.g., the positive subset selection problem from a set of $m$ vectors in $\mathbb{R}^n$, we propose a nonnegative UGA algorithm which needs $O(mn^2+ n^3/\epsilon^2)$ time to find a $\frac{1+\epsilon/\beta}{1-\epsilon/\beta}$-spectral sparsifier with positive coefficients with sparsity at most $\lceil\frac{n}{\epsilon^2}\rceil$, where $\beta$ is the ratio between the smallest length and largest length of the vectors. The convergence of the nonnegative UGA algorithm is established. For the graph sparsification problem, another UGA algorithm is proposed which can output a $\frac{1+O(\epsilon)}{1-O(\epsilon)}$-spectral sparsifier with $\lceil\frac{n}{\epsilon^2}\rceil$ edges in $O(m+n^2/\epsilon^2)$ time from a graph with $m$ edges and $n$ vertices under some mild assumptions. This is a linear time algorithm in terms of the number of edges that the community of graph sparsification is looking for. The best result in the literature to the knowledge of the authors is the existence of a deterministic algorithm which is almost linear, i.e. $O(m^{1+o(1)})$ for some $o(1)=O(\frac{(\log\log(m))^{2/3}}{\log^{1/3}(m)})$. Finally, extensive experimental results, including applications to graph clustering and least squares regression, show the effectiveness of proposed approaches.     

回载可分的闭环供应链配送中的多车辆运输策略

本文从车辆路径的角度研究了具有一个配送中心、多台车辆结合前向物流配送和逆向物流回载的闭环供应链运输策略,考虑回收产品的不同形态和可分批运输的特点,引入库存限制和成本惩罚,建立并分析了问题的数学模型．通过引入参数2σ原则构造了先分组后组内运用基于TSP的插入算法进行优化调整的启发式求解方法．算例分析表明该策略是合理有效的．     

A model to simplify 2D triangle meshes with irregular shapes

We present a 2D triangle mesh simplification model which is able to produce high quality approximations of any original planar mesh, regardless of the shape of the original mesh. This method consists of two phases: a self-organizing algorithm and a triangulation algorithm. The self-organizing algorithm is an unsupervised incremental clustering algorithm which provides us a set of nodes representing the best approximation of the original mesh. The triangulation algorithm reconstructs the simplified mesh from the planar points obtained by the self-organizing training process. Some examples are detailed with the purpose of demonstrating the ability of the model to perform the task of simplifying an original mesh with irregular shape.     

A QMR-based interior-point algorithm for solving linear programs

A new approach for the implementation of interior-point methods for solving linear programs is proposed. Its main feature is the iterative solution of the symmetric, but highly indefinite 2×2-block systems of linear equations that arise within the interior-point algorithm. These linear systems are solved by a symmetric variant of the quasi-minimal residual (QMR) algorithm, which is an iterative solver for general linear systems. The symmetric QMR algorithm can be combined with indefinite preconditioners, which is crucial for the efficient solution of highly indefinite linear systems, yet it still fully exploits the symmetry of the linear systems to be solved. To support the use of the symmetric QMR iteration, a novel stable reduction of the original unsymmetric 3×3-block systems to symmetric 2×2-block systems is introduced, and a measure for a low relative accuracy for the solution of these linear systems within the interior-point algorithm is proposed. Some indefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.     

弱偏好序下带容量房屋匹配混合模型的机制设计

研究弱偏好序下, 带容量房屋市场混合模型(CHMTeT)的机制设计问题, 并针对该模型提出了一类算法机制, 该机制是TTC算法机制的推广, 称之为剔除筛选算法(简记为CTTC)机制. 此外, 证明了CHMTeT模型应用CTTC算法得到的这一类机制(即CTTC机制)满足个人理性、帕累托有效性和防策略操纵性, 并得出CTTC算法的时间复杂度为O(n_{1}^{2}\\(n_{1}n_{2}+n_{2}^{2})), 其中n_{1}为参与人数, n_{2}为房子数.