装箱问题的概率近似算法

研究了一维装箱问题的在线近似算法,给出了一种新的半在线算法：随机适应算法（简称RF算法）,说明了RF算法的时间复杂度是O（n^2）,一般情况下的性能比〈1.75。     

关于图的领域复盖

图G＝（V，E）中一个点V的领域是点V及其邻点导出的G的子图。领域复盖问题就是求一级量小个的领域，使其复盖子G的每一条边。本文证明了无三角形图上和分离图上的领域复盖问题是NP－完全问题。通过研究集族的强Helly性质，得到了领域复盖问题可转化为团复盖问题的条件一图的领域二分具有强Helly性质。文中给出了弦图的领域二分图具有强Helly性质的禁用子图形式的充分必要条件。     

一类复合并行机排序问题计算复杂性研究

研究确定性排序理论的一个新模型：考虑４台机器的集合Ｍ＝（Ｍ１，Ｍ２，Ｍ３，Ｍ４）和ｎ个零件的集合Ｊ＝（ｊ１，ｊ２，…，ｊｎ），每个零件同时被２ｉ＝（ｉ＝０，１，２）台机器同时加工。证明了在不允许间断，优化指标为作业排序长度的条件下，该问题是强ＮＰ－完全问题，没有多项式时间算法。     

赋有提前或延误惩罚的单机排序问题的动态规划算法

Ｌａｗｌｅｒ和Ｌｅｎｓｔｒａ已证明［１］：赋有延误惩罚的单机排序问题是强ＮＰ－完全问题，没有多项式时间算法。笔者曾证明［２］：如果附加条件ｐｉ≥ｐＪｐｉ／ｗｉ＞ｐｊ／ｗｊ对于所有的ｉ≠ｊ（ｉ，ｊ＝１，２，…，ｎ）成立，则该问题有伪多项式时间算法。现在研究如何用动态规划方法求解这类排序问题。     

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

最小顶点覆盖是图论中的一个重要概念，它是一个NP难的问题．给出了一个求解最小顶点覆盖的近似算法，与现有算法相比具有更优的性能比。     

关于Szasz的问题12和问题13

Szasz FA提出下列两个公开问题.(1)求根性R对任意环A和A的任意两个理想I_1,I_2满足R(I_1 I_2)=R(I_1) R(I_2)的充分必要条件(即Szasz的问题12).(2)求根性R对任意环A和A的任意两个理想I_1,I_2满足(I_1∩I_2)=I_1∩I_2的充分必要条件(即Szasz的问题13).本文引入σ—根和τ—根,利用σ—根和τ—根分别给出了上述两个问题的充分必要条件.     

DNA计算问题的研究进展

DNA计算是近十年发展起来的一门新学科,目前的研究已经取得了很大的进展.本文首先介绍了DNA计算的机理,然后说明了DNA分子的结构及DNA计算的特点.最后分析了目前DNA计算所存在的问题,并展望了DNA计算的应用发展前景.     

单机排序问题1｜P_k≥P_qP_k／W_k＞P_q／W_q｜sum from q＝1 to n of （…）W_q｜c_q－d_q｜近似最优解的伪多项式时间算法

Ｌａｗｌｅｒ和Ｌｅｎｓｔｒａ已证明［１］：单机排序问题１‖ｎｑ＝１Ｗｑｍａｘ｛（ｃｑ－ｄｑ），０｝是“强”ＮＰ完全的。而该问题是１‖ｎｑ＝１Ｗｑ｜ｃｑ－ｄｑ｜的子问题，因而也是强ＮＰ完全问题，没有好算法。本文在假设Ｐｋ≥ＰｑＰｋ／Ｗｋ＞Ｐｑ／Ｗｑ成立的条件下，设计出求该问题的近似最优解的伪多项式时间算法。     

旅行商问题图论近似算法有效性分析

给出旅行商问题四种图论近似算法及有效性分析,改进第一种近似算法证明,修正第二、三、四种近似算法有效性的上界。     

一个描述内存工作区操作的公理语义方法

本文定义了一个内存工作区处理语言ＭＰＬ，并提出了用于描述语言的形式化方法，作为示例，文中最后给出一个程序部分正确性的验证提纲。     

强伪压缩映射不动点的迭代逼近

在实一致光滑的Banach空间上，用逼近方法证明了关于两个多值强伪压缩映射不动点的带误差的Ishikawa迭代序列的收敛性，该结果改进并推广了巳有的结果。     

一类求解CSP问题的混合算法

在研究了各种求解CSP问题方法的基础上,提出了一个基于分层技术的混合算法,从理论上分析了该方法能以少的代价来缩小搜索空间,并且能求出全部解的特点.最后用一个经典问题——皇后问题作为例证,求解的结果表明该方法是有效的.     

工件带准备时间的平行机调度问题的一个近似算法

提出了一个启发式算法,在该算法中,工件中断的次数至多为2N次,计算的复杂度为O(Nnlogn),并以一个实例加以说明.证明了对某些特殊的实例,该算法能够得到最优调度.指出了对于一般情况该算法的最坏情况误差界为(2(n-1))/n.     

两个带时间限制的作业调度算法

在目前最常见的带时间限制的作业调度模型上给出两个作业调度算法，（１）当限制每个作业加工时间为单位时间时，给出一时间复杂性为Ｏ（ｕｍ）１．５）的最佳作业调度算法；（２）对作业加工时间为非单位时间的一般情况，证明了求最佳作业调度问题是一ＮＰ－完全问题，并给出一时间复杂性为Ｏ（ｍａｘ｛ｎｌｏｇｎ，ｕｐ｝）的近似算法，这里ｎ，ｐ，ｍ分别表示作业的个数、机器的台数，［１～ｍ］为调度的时间区间．     

强非线性复合材料中的原胞有效媒质近似

本文提出了原胞有效煤质近似（ＣＥＭＡ）来研究强非线性复合导体的有效非线性响 应．在该复合介质内，各组分的电流密度与电场关系满足，式中ｘ是非线性响应．这 个原胞模型由两种原胞组成，一种是由核和壳组成的复合原胞，另一种是由单相组成的简单原 胞．研究的基础是把变化原理和有效媒质理论相结合应用于集合原胞系统中．ＣＥＭＡ提出了一 个适用于强非线性复合介质的一般形式．     

关于一类广义非线性变分不等式组的新逼近算法

引入了一类新的广义非线性变分不等级组的新逼近算法，讨论了其解的存在性，同时给出了逼近解的迭代算法及收敛性分析。     

伪压缩型映象迭代逼近的收敛性问题

研究一类伪压缩型映象迭代逼近的收敛性问题，其结果改进和推广了已有结果．     

广义强非线性拟变分不等式和拟补问题解的扰动算法

本文进一步研究了由第一作者引入和研究的一类广义强非线性拟变分不等式和拟补问题．在另一类假设条件下证明了解的存在性，提出了一类新的求近似解的迭代算法——扰动算法，证明了扰动近似解序列强收敛于精确解