一个瓶颈问题的多项式算法

在生产安排中会遇到这样问题:确定满足约束条件x_1+…+x_n=m的正整向量X=(x_1,…,x_n),使目标函数y=min{c_jx_i)达到最大。罗宗俊曾给出这个问题的一个拟多项式算法,大约需要n(m-n)次运算。本文给出一个多项式算法,仅需要n·log_2n次运算。     

具第二类Chebyshev节点的拟和扩充Hermite-Fejer插值算子的逼近度

设U_n(x)=(sin(n 1)θ)/(sinθ)(x=cosθ)是第二类Chebyshev多项式,b_k=b_k~(n)=cos((kπ)/(n 1))(k=1,2,……n)是U_n(x)的零点,以{-1,b_1……,b_n,1}为基点的2n 1次拟Hermite-Fejer插值多项式是     

关于问题1|chains,B|Cmax的多项式算法

对带有"扩充链"优先约束的分批排序问题进行了研究,其目标函数为最大完工时间.优先约束为:在一个"扩充链"上包含有n个工件,另外有m个孤立点工件(即工件之间无任何优先约束).讨论了B=2时问题的最优算法,把这一问题多项式转化成了组合最优化中求解非二部图赋权匹配问题,并相应地给出了一个运算次数为O(n4)的多项式算法.     

拉格朗日插值多项式的一种并行算法

提出在机群系统并行环境下的构造拉格朗日插值多项式的一种并行算法.该算法以n个节点(x0,y0),(x1,y1),…,(xn-1,yn-1)的拉格朗日插值多项式公式为基础.当处理机数量为n2时,它的时间复杂度为3log(n) O(1);当处理机数量为p2(p相似文献   

P_n~k和T_((k_1,k_2,…,k_n))的色多项式

本文研究了图Pnk和T(k1,k2,…,kn)的色多项式,得到P2n、P3n和T(k1,k2,…,kn)的色多项式递推公式,以及Pn2仅当n≤4时是色唯一图,T(k1,k2,…,kn)仅当n=1是色唯一图等结论.     

Pkn和T(k1,k2,…,kn)的色多项式

本文研究了图Pkn和T(k1,k2,…,kn)的色多项式,得到P2n、P3n和T(k1,k2,…,kn)的色多项式递推公式,以及P2n仅当n≤4时是色唯一图,T(k1,k2,…,kn)仅当n=1是色唯一图等结论.     

多项式xn-1在有限域Fp上的因式分解

令p为奇素数,给出了多项式x~n-1在有限域F_p上的一个不可约分解的有效算法.考虑n=d(p+1)的情形,其中d|(p-1)且dp-1.在此类情况下,其分解问题可以借助F_p上的一个本原多项式,由Dickson多项式完全给出.最后用实例对算法加以说明.     

一类背包问题的可解性

本文的主要结果是,对K背包问题给出了时间、空间复杂性为O(nM~k)的拟多项式算法;证明了若P≠NP,则该问题不存在完全多项式时间ε近似算法;对动态背包问题给出了时间复杂性为O(nM~k)的拟多项式算法。     

Fp上不可约与本原多项式的高效确定算法

对于一大类整数n(n为素数乘于素数或1的积),分别给出有限域Fp上n次多项式是不可约多项式与本原多项式的一个充要条件,该条件可通过O(n3)次Fp上乘法加以验证,易于硬件实现.提出可约多项式一个充分条件,借此减少验证时间,并得到用O(n4)次Fp上乘法确定一个n次不可约多项式及一个n次本原多项式的高效算法.对于ECC中构造Fnp上椭圆曲线、序列密码中构造LFSR,有重要的应用价值.     

具有第二类Chebyshev零点的Hermite-Fejér插值算子的渐近估计式

设Rn[f;x]和Hn[f;x]分别为以第二类Chebyshev多项式Un(x)的零点b_k=cos(kπ/(n U),k=1,2,…,n作为结点的Hermite-Fejr插值算子和拟Hermite-Fejr插值多项式,我们得到两个定理。     

关于概率多项式时间谱系的一些结果

研究概率多项式时间谱系的结构性质,证明了:(1)如果BP∑_(k+1)~pBP∑_k~P,则PH=BP∑∏_K~P;(2)如果BP∑_k~PBP∏_k~P,则;PH=BP∑_K~PP;(3)对任意n,k≥0,BP∑_K~P(BP∑_n~P)=BP∑_(n+k)~p,BP∑_n~P(BP△_(k+1)~P)=BP∑_(n+k)~n;(4)对任意n,k≥1,BP∑_n~P(BP∑_k~p∩BP∏_k~P)=BP∑_(n+k-1)~P这些结果说明概率多项式时间谱系与多项式时间谱系有相同的结构性盾,但也有差别.     

限制性的带核元划分问题

考虑了限制性的带核元划分问题,即将一个整数集合划分为2个子集,使得2个核元分别在不同的子集里且每个子集至多包含k个元素,这里n/2+1≤k≤n+1,目标使2个子集中元素之和的最小者达尽可能大.对一般的k,给出了全多项式时间近似方案(FPTAS).当k=n+1时,给出了线性时间内的多项式时间近似方案(PTAS)和全多项式时间近似方案(FPTAS).     

资源约束排序问题Qm|res1·1,pj=1|∑Cj

讨论了一类恒速机可再生离散资源约束排序问题Qm|res1·1 ,pj=1 | Cj,把它转化成能用多项式时间算法求解的瓶颈运输问题     

关于图染色的算法

本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」.     

带有扩充链优先约束工件的分批排序问题

提出一种工具之间带有扩充链的优先约束的分批排序问题,这种扩充链上既有优先序工件又有无约束工件(工件个数不定)。目标为极小化最大完工时间。优先约束为有m个优先约束集,其中一个"扩充链"上有n个工件,其余m-1条链上的工件数为常数,工件的加工不可中断。问题1chains,B=mCmax为多项式可解,同时给出了问题的一个多项式算法。     

工件加工时间的可控排序问题

讨论离散加工时间可控的排序问题P｜dis_cpt，pmtn｜ n∑j=1Cjtj＋Cmax,应用线性规划松弛方法得到其性能比为e/e-1（≈1.583）多项式时间近似算法.     

工时随开工时间递增的成组排序问题

讨论了一类工件的加工时间随工件的开工时间线性递增的成组排序问题1|pij=bij aijt,S=sf,GT|Cmax,给出了求最优解的多项式时间算法.     

一类机器带时间限制的分批排序问题及算法

机器带有时间约束的分批排序问题是一类新型排序问题。本文首次对1,R|B≥n|∑Cj问题进行了研究。并给出了一个伪多项式时间动态规划算法。     

n元m阶方阵的k次方幂和的一种新算法

文中用初等对称多项式来表示特殊对称多项式sk(x1,x2,…,xn)=sum xik from i=1 to n (k=0,1,2,…)方法得到了n元m阶方阵的k次方和sk=sum xik from i=1 to n (k=0,1,2,…)类似的公式,并对其的计算问题进行了研究,得出了一系列结论.     

丢番图方程n∑k=1k4=ny2,n∑k=1k3=np1p2…pmy2以及n∑k=1k5=ny2

多项式整数值中的完全方幂问题,是数论中引人关注的研究课题.本文利用pell方程解的性质,给出了丢番图方程n∑k=1k4=ny2,n∑k=1k3=np1p2…pmy2以及n∑k=1k5=ny2的所有正整数解.