拟阵交约束分划

给出了用求量大重量拟阵交算法来求定形拟阵交２－分划问题的最优解的一个充分条件。     

单台机订单排序的在线与半在线算法

考虑了一类新的单台机在线模型－订单在线和半在线排序问题，证明了对于单台机的半在线模型，有R（1，MLS）≤1 r/1 r。     

拟阵基图的1-Hamilton 性质

研究了拟阵基图的１－Ｈａｍｉｌｔｏｎ性质,证明了基图或者是１－Ｈａｍｉｌｔｏｎ连通的,或者是一个超方体,或者与Ｋ２×Ｋ３和５轮Ｗ５中之一同构。     

平行机排序作业中具有不同开机时间的MF算法

安排ｎ个独立工件在ｍ台相同平行机上作业、使总的完工时间最少。其中工件元准备时间,但机器的开机时间不同,ＬＰＴ和ＭＬＰＴ算法分别具有３／２－１／２ｍ和４／３的最坏性能比。这里证明了ＭＦ算法的最坏性能比不大于９／７。     

图的子图中(n,r)-正交因子分解

设图G的顶点集为V(G)，边集为E(G)，g和f是定义在V(G)上的2个整值函数，满足对于一切x∈V(G)，g(x)≤f(x).若G是一个(mg+rn，mf-rn)-图，1≤n＜m，r≥2，且对于x∈V(G)，有g(x)≥k≥1，则存在G的一个子图G′，使得G′具有一个(f，g)-因子(n，r)-正交于G的任意给定子图H，其中｜E(H)｜=nk.     

Harary图的最优Super-λ性质

在给定的顶点数n和边数e的所有图中，Harary图有最大的连通度[2e/n]，因此它是一个较好的网络模型，给出了Harary图的可靠性分析，证明了它是最优Super-λ图；而且精确地计算了它的限制性边连通度和i-边割集的数目mi。     

FFD(L)≤11/9OPT(L)+7/9

一维装箱问题可定义为:给定一个代表工件大小的正数表(为方便计p_ⅰ也表第ⅰ个工件),如何把这些工件装入大小为单位容量的箱子里去,使所用的箱子数最小。FFD(first fit decreasing)算法是装箱问题的一个近似算法。FFD算法是指:首先按工件大小将工件排队,然后从大的开始装入箱内.不妨设,当装第ⅰ个工件p_ⅰ时,B_k是下标最小且其中装入的工件的大小总量不超过1-p_ⅰ的箱子,那么FFD算法就将p_ⅰ放入箱子B_k中。用FFD(L)表示用FFD装L中的工件所用的箱子数。OPT(L)表示最优装法所用的箱子数。Johnson证明了成立,Baker证明了越民义证明了,本文利用权函数证明了