带点弧约束的最短路问题：复杂性和算法

本文首先提出了带点弧约束的最短路问题，证明了该问题属于ＮＰ－Ｃ，然后给出了一个伪多项式时间算法．最后给出了最小成本最短路问题的一个时间复杂性为Ｏ（ｎ２）的算法．     

二次规划的内椭球算法

对于标准型的凸二次规划问题本文给出了一个新算法，算法的一每步迭代，利用内椭球的思想来近似求解一个线性质规划子问题而得到迭代方向，再适当选取步长而使之成为多项式算法，其迭代步数为Ｏ（ｎＬ＾２），每一步迭代所需计算量为Ｏ（ｎ＾３）。其中ｎ为变量个数，Ｌ为问题的输入长度。     

分派问题一种标号算法

文章采用一定技巧,把求最短路的Ｄｉｊｋｓｔｒａ算法用于求解分派问题,得到一种标号算法,计算复杂性仅为Ｏ（ｎ２）,比以往的算法减少了一个数量阶Ｏ（ｎ）。     

带多重选择的最短路问题:复杂性和算法

本文提出了带出重选择的是短路问题,建立了该问题的数学模型,利用背包问题的一个变形问题－带限制选择的背包问题,证明了该问题是ＮＰ－Ｃ的,最后利用动态规则给出了一个伪多项式算法,其时间复杂性Ｏ（Ｃｈｍｎ）,其中ｈ是最大的选择重数。     

关于最短路问题的一个双目标优化问题

本文研究了一个双目标最短路问题的变形问题,在该变形问题中,一个目标函数还是路的长度,另一个目标函数则是路的容量,在Pareto-optimal最优解的意义下,本文给出了一个时间复杂性为O（n^3 )的算法,在字典序最优解的意义下,本文给出了一个时间复杂性为O(n^3)的算法。     

一类组合最优化问题及其算法

本文介绍三个新的组合最优化模型，并分别给出复杂性为Ｏ（Ｎ２）和Ｏ（Ｎ２α）的多项式算法和拟多项式算法．     

直径为2的图的P2路色问题

一个给定的图是否存在用ｒ种颜色的正常Ｐｋ着色？称该问题为图的（ｋ，ｒ）路色数问题。已知对于直径为２的图及任意给定的整数ｒ≥３，图的（２，ｒ）路色数问题是ＮＰ－完全的。本文给出直径为２的（２，２）路色图的一个好的刻划，并由此给出该问题的一个多项式时间算法，从而解决了以ｒ为参数的直径为２的图的（２，ｒ）路色数问题的计算复杂性分类。     

最大流问题的逆问题

讨论了最大流问题的逆问题,提出了ｆ＾０截的概念,给出并证明了逆问题有解的充要条件;当逆问题有解时,把逆问题转化为找一个容量网络的最小截的问题;最后,给出了一个复杂度为Ｏ（│Ｖ│＾３）的多项式算法。     

求最短路径树的一个新算法

本文考虑在一个具有ｎ个结点和ｍ条弧的网络中，求出从一个指定的结到其余所有结点的最短路径，或者找到一条具有负长度环路的问题，文中基于结点标号深度的概念，给出一个计算复杂性的界为Ｏ（ｎｍ）并且具有“尖利”（ｓｈａｒｐ）性质的求最短路径树的新算法。此外，我们还讨论了负长度环路的探测问题，并给出了一个具有“时间尖利”（ｔｉｍｅ－ｓｈａｒｐ）性质的检测负长度环路的方法。     

P.Turan问题XXXV的一个注记

本文给出了有关Ｐ．Ｔｕｒａｎ问题ＸＸＸＶ［关于逼过论的某些未解决的问题，Ｊ．Ａｐｐｒｏｘｉｍａｔｉｏｎ Ｔｈｅｏｒｙ，１９８０，２９（１）：２３－８５］的一个结果。设ｒｉｎ（ｘ）为（０，２）插值的第一类基函数，其插值节点为（１－ｘ）Ｐｎ＇（ｘ）之零点而Ｐｎ（ｘ）为ｎ次Ｌｅｇｅｎｄｒｅ多项式。那么ｍａｘ－１≤ｘ≤１∑ｉ＝１ｎ│ｒｉｎ（ｘ）│＝Ｏ（ｎ＾５／２ｌｎｎ）．但对ｆ＾＊＝ｘ＾２却有ｌｉｍ↓ｎ→     

二维输运方程离散格式的对称性

讨论了二维柱几何非定态中子输运方程离散格式的对称性问题，在几何空间和相空间连续的情况下，证明了时间离散方程的一维球对称性；而在时间和相空间离散的情况下，阐述了格式不具有一维球对称性；对时间和相空间离散情况下的几何空间间断有限元方程，得到了左右对称性。     

军需物资调集规划问题的研究

以军需物资调集为背景 ,在系统分析的基础上建立了全局优化问题的数学规划模型 ,并对模型求解进行了研究 ,提出两阶段规划算法 .仿真计算结果表明所建模型的有效性     

移位交换网的最优路由算法

移位交换网是重要的互联网络之一 ,在并行计算中有着广泛应用 .然而 ,它缺少任意点对间的最短路由算法 .已有的路由算法都不能保证其任意节点对间都是最短路由 .文中给出了一个最短路由算法 ,也是最优路由算法 ,它使得从源节点到目的节点的任何信息都是沿最短路由传输 .同时 ,我们还得到了任意节点对间的距离公式     

带有未知输入的降阶观测器的设计

本文讨论了带未知输入的线性时不变系统的状态重构问题 .在一种特定的坐标变换下 ,给定了该系统存在降阶观测器的充分必要条件 .与已有结果相比 ,该条件比相应的文献所给出的条件弱 ,并且本文的条件是系统本身的 ,因而也更合理     

匹配问题实例空间和解空间结构

本文通过研究匹配问题的实例空间，匈牙利算法和解空间三者之间的关系，指出S实例空间的数目与问题复杂度之间的关系既不是充分也不是必要的，而如何对问题的解空间进行合理的分解才能是问题的关键。     

全稳定Q过程构造的一个等价条件

给出了Q过程构造的等价条件,证明了Q过程的构造等价于一个条件方程组的解,以此方法求出了所有的Q过程、F过程、B过程及BF过程的等价条件。     

线性齐次常微分方程(组)的λ-矩阵求解法

本文在文 [2 ]的基础上 ,应用λ-矩阵及微分算子性质给出了一种变系数齐次常微分线性方程 (组 )的λ-矩阵求解法 ,对文 [2 ]作出了更一般的推广 .     

分形整合过程在经济预测中的应用

首先采用一个分形整合模型——误差逗留模型 (Error-Duration Model)仔细推导了分形时间序列过程的性质 ,特别是序列自相关系数的性质 ,表明分形整合过程与常规的时间序列分析工具有很大的不同 ;然后以一个实际的时间序列为例 ,说明了分形整合过程在经济预测中的应用比传统的分析工具有较好的预测精度     

完美匹配树的次大和次小的最大特征值

本文讨论完美匹配树的次大和次小的最大特征值问题,得到了次大的最大特征值的上界的明确表达式并确定了达到此上界的极树,同时也得到了次小的最大特征值的下界并确定了相应的极树。     

A discrete algorithm for localizing the discontinuity lines of a function of two variables

We consider an ill-posed problem of localizing the discontinuity lines of a function of two variables. It is assumed that, instead of a precisely given function f, the values are available of the averages on the square of the perturbed function f^δ at the points of a uniform grid as well as the error level δ so that \({\left\| {f - {f^\delta }} \right\|_{{L_2}}}{(_\mathbb{R}}^2)\) ≤ δ. An algorithm is constructed for localizing the discontinuity lines, its convergence is proved with the estimates of the approximation accuracy, which coincide in the order of magnitude with the estimates obtained earlier by the authors for the case when, instead of the average values of the function f^δ, the function itself is given. Also, we substantiate the estimates for an important characteristic of localization methods, i.e. separability threshold.