关于整数向量卷积的一个算法的时间复杂度

众所周知,两个n维整数向量循环卷积的常规算法(即按定义计算)的时间复杂度为O(n~2),现在已有时间复杂度为O(nlog_2n)的快速算法,[1]中提出一个新算法,称其时间复杂度为O(n),因而是最佳的。 本文首先指出[1]的错误原因,再根据算法分析理论得出[1]中算法的时间复杂度不低于O(n~2log_2n),因而比常规算法的运算量还大。     

顶点加权最大团问题的加权分治算法

分支降阶被广泛用来求解NP-Hard问题,该技术的核心思想是将原问题分解成若干个子问题并递归求解这些子问题,但是用来分析算法时间复杂度的常规分析技术不够精确,无法得到较好的时间复杂度.本文设计了一个基于分支降阶的递归算法求解加权最大团问题,对于提出的精确算法,首先运用常规技术对该算法进行时间复杂度分析,得出其时间复杂度为O(1.4656~np(n)),其中n代表图中结点总个数,p(n)代表n的多项式函数;然后运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂性由原来的O(1.4656~np(n))降为O(1.3765~np(n)).研究结果表明运用加权分治技术能够得到较为精确的时间复杂度.     

(X+K) mod2n运算和X(+)K运算异或差值的概率分析及其应用

对(X+ K) mod 2n运算和X(+)K运算异或差值函数的概率分布规律进行了研究,并基于穷举攻击中“大概率优先选取”原则,给出了一个解决(X+K) mod 2n和X(+)K等价问题的计算复杂度为O(n)的算法,基于此对Hawkes等人针对SNOW1.0的猜测决定攻击进行了改进,使其数据量由O(295)降为O(290),而计算复杂度由O(2224)略微提高到O(2224.482).     

一种基于能量的RNA二级结构预测的动态划分算法

预测单链RNA分子序列的二级结构是计算生物学中的一个重要内容.本文基于RNA分子结构的稳定性原理.提出了一种预测RNA二级结构的新算法——基于能量的动态划分算法.该算法的空间复杂度仅为O(n),时间复杂度近似为O(n2·logn),且预测结构有较好的精度.     

计算周期三对角矩阵行列式和逆矩阵的新算法

给出了一种计算周期三对角矩阵行列式和逆矩阵的新递推算法,它们的运算复杂度分别为O(n)和O(n2),该算法是文献[5]和[6]中相关算法的拓广.     

一个约束乘积最大问题的强多项式时间算法

本文讨论了约束乘积最大问题最优解的结构特征,在此基础上给出了一个计算时间为O(n2)的强多项式时间算法,并且对于单边约束的情形给出了复杂度更低(O(nlnn))的强多项式时间算法.     

具有有界变量的瓶颈分配问题的一个并行算法(英文)

本文提出一并行算法求解具有优个约束以及n个非负有界变量的瓶颈资源分配问题,若有m台处理机,在一定条件下该并行算法的复杂度为O(n(n+logm))。     

(X+K)mod 2~n运算和XK运算异或差值的概率分析及其应用

对(X+K)mod 2~n运算和X⊕K运算异或差值函数的概率分布规律进行了研究,并基于穷举攻击中大概率优先选取原则,给出了一个解决(X+K)mod 2~n和X⊕K等价问题的计算复杂度为O(n)的算法,基于此对Hawkes等人针对SNOW1.0的猜测决定攻击进行了改进,使其数据量由O(2~(95))降为O(2~(90)),而计算复杂度由O(2~(224))略微提高到O(2~(224.482)).     

模糊环境下的最优装载问题

将动态规划中的一维背包问题推广到了n维,并利用模糊数为工具,在模糊环境下给出了n维背包问题的最优解,最后通过实例说明该方法的简便、有效和实用性.     

WDM网络中的一个改进的最优半光通道路由算法

本文在一个限定的条件下，提出了一个WDM网络中的寻找最优半光通道算法，使时间复杂度从O（k^2n km knlog(kn))提高到O（k^2n km nlogn)。     

O(n) Procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates

Summary In this paper, we describe computationally efficient procedures for identifying all maximal cliques and non-dominated selected subsets of extensions of minimal covers and alternates that are implied by single 0–1 knapsack constraints. The induced inequalities are satisfied by and 0–1 feasible solution to the knapsack constraint, but are tipically violated by fractional solutions. In addition, the procedures described here are used in conjunction with other constraints to further tighten LP relaxations of 0–1 programs. The complexity of the procedures isO(n). Part of this work has been done while the author was at IBM Research, T.J. Watson Research Center, NY, USA.     

可分离的二次背包问题的一种直接算法

研究了可分离二次背包问题的一种直接算法.此类背包问题的目标函数是二次的,且含有严格的一次项,其不等式约束是线性的.给出所求模型的一般形式,经过预处理该模型,最终归为求解两类问题（P1）和（P2）.重点是求解（P2）问题的最优解,通过分析（P2）问题的结构特点,假设固定一次项后问题的最优解和相应不等式的拉格朗日乘子已求出,通过比较拉格朗日乘子和（P2）问题的一次项系数来调节λ的大小,从而求出（P2）问题的最优解.对于（P1）问题,改进了Bretthauer和Shetty给出的算法（Bretthauer K M,Shetty B.A pegging algorithm for the nonlinear resource allocation problem.Computers and Operations Research,2002,29（5）：505-527）.此算法的计算复杂性为O（n）.数值算例表明,将这种固定变量算法和文中的定理5结合起来,能够快速有效地求解此类更一般的二次背包问题.     

A Newton’s method for the continuous quadratic knapsack problem

We introduce a new efficient method to solve the continuous quadratic knapsack problem. This is a highly structured quadratic program that appears in different contexts. The method converges after $O(n)$ iterations with overall arithmetic complexity $O(n^2)$ . Numerical experiments show that in practice the method converges in a small number of iterations with overall linear complexity, and is faster than the state-of-the-art algorithms based on median finding, variable fixing, and secant techniques.     

Issues in the implementation of the DSD algorithm for the traffic assignment problem

In this paper we consider the practical implementation of the disaggregated simplicial decomposition (DSD) algorithm for the traffic assignment problem. It is a column generation method that at each step has to solve a huge number of quadratic knapsack problems (QKP). We propose a Newton-like method to solve the QKP when the quadratic functional is convex but not necessarily strictly. Our O(n) algorithm does not improve the complexity of the current methods but extends them to a more general case and is better suited for reoptimization and so a good option for the DSD algorithm. It also allows the solution of many QKP’s simultaneously in a vectorial or parallel way.     

A correction of the justification of the Dietrich-escudero-garín-pérez O(n) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates

Summary In this brief note we present a correction of the Propositions 1 and 5 for proving the O(n) complexity of the algorithms described in [Dietrich et al. (1993)] for identifying maximal cliques and non-dominated covers from extensions of consecutive minimal covers and alternates implied by 0–1 knapsack constraints.     

On using an automatic scheme for obtaining the convex hull defining inequalities of a Weismantel 0–1 knapsack constraint

In this short note we obtain the full set of inequalities that define the convex hull of a 0–1 knapsack constraint presented in Weismantel (1997). For that purpose we use our O(n) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates, as well as our schemes for coefficient increase based tightening cover induced inequalities and coefficient reduction based tightening general 0–1 knapsack constraints.     

关于矩阵乘法的一个改进算法的时间复杂度

两个ｎ阶非负整数方阵相乘,常规算法的时间复杂度为Ｏ（ｎ^３）,文献［１］提出一个“运算次数”为Ｏ（ｎ²）的“最佳”算法,文献［２］对此算法做了进一步研究,提出三种改进策略．本文根据算法分析理论,得出改进后的算法的时间复杂度仍不低于Ｏ（ｎ^３ｌｏｇｎ）,因而其阶仍高于常规算法的运算量的阶．     

关于矩阵乘法的一个算法的时间复杂度

两个n阶非负整数方阵相乘,常规算法的时间复杂度为O(n³),文献[1]提出一个“运算次数”为O(n²)的“最佳”算法,本文根据算法分析理论得出此算法的时间复杂度不低于O(n³log₂ⁿ),因而比常规算法的运算量还大.     

A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems

This paper considers a general class of continuous, nonlinear, and nonseparable knapsack problems, special cases of which arise in numerous operations and financial contexts. We develop important properties of optimal solutions for this problem class, based on the properties of a closely related class of linear programs. Using these properties, we provide a solution method that runs in polynomial time in the number of decision variables, while also depending on the time required to solve a particular one-dimensional optimization problem. Thus, for the many applications in which this one-dimensional function is reasonably well behaved (e.g., unimodal), the resulting algorithm runs in polynomial time. We next develop a related solution approach to a class of continuous, nonlinear, and nonseparable multiple-choice knapsack problems. This algorithm runs in polynomial time in both the number of variables and the number of variants per item, while again dependent on the complexity of the same one-dimensional optimization problem as for the knapsack problem. Computational testing demonstrates the power of the proposed algorithms over a commercial global optimization software package.