带有拒绝工件和机器具有不可用区间的单机排序问题

本文考虑带有拒绝工件和机器具有不可用区间的单机排序问题。目标是最小化被接受工件的特定加权总完工时间与被拒绝工件总费用的和。工件有不同的释放时间和权,权等于它们的加工时间。这个问题是一般NP-难的。为了能在较少的运行时间内得到该问题较好的近似解,利用削减状态空间的方法得到了一个全多项式时间近似方案(FPTAS),该FPTAS是一个具有强多项式运行时间的较优近似方案,其时间复杂性为O(n3/ε2),其中n为输入工件的个数,ε是误差界。     

带有不可用区间中断可恢复的平行机排序问题

讨论带有不可用区间且工件中断可恢复的两台平行机排序问题。其中一台机器带有不可用区间,在不可用区间内不能加工工件。工件在加工时被不可用区间中断后,可以在不可用区间之后继续加工。目标是最小化加权总完工时间。这个问题是一般定义下NP-难的,因此需要寻找满足指定精确度的近似解。首先给出全多项式近似方案的定义,其次提出了一个动态规划的算法,最后利用划分程序的方法得到了一个全多项式近似方案(FPTAS),该近似方案的时间复杂性为O(n5 L5/ε4),其中:n为输入工件的个数;L为输入规模;ε0为误差精度。     

一种在欧氏空间设计多项式时间近似方案的新技术

提出了一种在欧氏平面上设计多项式时间近似方案的新技术．应用该技术设计多项式近似方案分为两步：(1)对欧氏平面进行随机分割；(2)对随机分割的结果利用动态规划技术计算近似最优解．近年来Arora利用该技术获得了TSP，Steiner树，K-median三个著名NP—hard问题的多项式近似方案．经验表明，该技术适用于欧氏平面上对“距离和”优化的NP—hard问题，并可十分容易地推广到多维欧氏空间．     

一种在欧氏空间设计多项式时间近似方案的新技术

提出了一种在欧氏平面上设计多项式时间近似方案的新技术．应用该技术设计多项式近似方案分为两步：(1)对欧氏平面进行随机分割；(2)对随机分割的结果利用动态规划技术计算近似最优解．近年来Arora利用该技术获得了TSP，Steiner树，K-median三个著名NP-hard问题的多项式近似方案．经验表明，该技术适用于欧氏平面上对“距离和”优化的NP-hard问题，并可十分容易地推广到多维欧氏空间．     

子集和问题中的一个重要定理

令f为n元多项式,A1,A2, ,An为复数集C的有穷子集,F=｛a1+a2+ +an:ai∈Ai,f(a1, ,an)≠0｝,若对任意1≤i≤n,均有｜Ai｜>degif,证明了｜F｜≥1+∑n｜Ai｜-i=1∑ndegif-n.推广了子集和问题中的一个重要结果.i=1     

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

研究概率多项式时间谱系的结构性质,证明了:(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这些结果说明概率多项式时间谱系与多项式时间谱系有相同的结构性盾,但也有差别.     

有限域F2n上的一些置换多项式（英文）

给出有限域F2 n上形如f(x)=(x2 k+x+δ)s+x的多项式为置换多项式的几个充分条件.     

带有拒绝工件和机器维修区间的单机排序问题 (运筹学与控制论)

考虑带有拒绝工件和机器维修区间的单机排序问题。目标是最小化被加工工件的总完工时间与被拒绝工件的总惩罚(被拒绝加工的工件需要支付拒绝惩罚)的和。这个问题是一般意义下NP-难的,因此需要快速寻找满足指定精确度要求的近似解。为了能在较少的运行时间内得到该问题的较好的近似解,利用削减状态空间方法得到了一个全多项式时间近似方案(FPTAS)。该FPTAS是一个具有强多项式运行时间的较优近似方案,其时间复杂性为O(n2/ε2),其中n为输入工件的个数,ε>0为任意小的实数。     

关于N的一类U-划分及性质

设U={u_n|n≥1}是自然数集N的子集,其元由u_(n+2)=u_(n+1)+u_n+h定义。本文证明了N的子集M={k∈N|1≤k相似文献   

一类双约束最短路问题的近似算法

带时间和边数约束的双约束最短路问题是NP-完备的。它的一种拟多项式精确算法可以利用动态规划方法给出，在此基础上采用rounding和scaling的处理技术得到了一种全多项式时间近似方案（FPAS）。     

关于若干整数分拆问题

Y．Alavi,A．J．Boals,G．Chartrand,P．ErdSs和O．R．Oellermann提出下面的猜想：已知整数a1,a2,…,ak,满足n≤ai≤2n-2,1≤i≤k,且a1＋a2＋…＋ak=rt（n＋1）／2,则S=（1,2,…,n）包含有k个互不相交子集S1,S2,…,Sk,满足ai=∑（Si）,1≤i≤k。推广该猜想,得到下面的定理：已知整数a1,a2,…,ak,满足ai≥n,1≤i≤k,且a1＋a2＋…＋a4≤n（n＋1）／2,则S={1,2,…,n）包含有k个互不相交子集．S1,S2,…,Sk,满足ai=∑（Si）,1≤i≤k。由此定理易推出K．Ando,S．Gervacio和M．Kano证明的一个主要定理。参考文献中的一个错误同时被更正。     

限制偏导数的函数的多项式逼近

<正> 1.引言在一元函数中用一个与它单调性相同的多项式来逼近的问题已经有许多数学工作者作了精辟的论述[1——16]。作者在[17]中研究了二维偏单调函数的共单调多项式逼近。本文研究了限制偏导数的函数的多项式逼近,得出了与偏共单调逼近有关的一些结论。     

二项式系数的均值不等式

本文得到二项式系数的算术与几何平均值不等式以及广义积分插入。(1)Gn+1≤{P∫∞0[∏nk=0(x+nk)qk]-p-1dx}-1/p≤An+1;(2)e≤limn→∞{P∫∞0[∏nk=0(x+nk)]-(p+1)/n+1dx}-1/p≤2;(3)Gn+1≤J(a,q,p)≤J(a,q,p,l,λ)≤An+1在此,J(a,q,p)={P∫∞0[∏nk=0(x+nk)qk]-p-1dx}-1/p;J(a,q,p,l,λ)={P∫∞0λ-1[∏nk=0(l+λ(x+nk))qk-l]-P-1dx}-1/p     

一类单圈图的谱半径的序

按照谱半径对一类单圈图C_(n,2)进行了排序,得到ρ(C_(n,2)～1)≤ρ(C_(n,2)～2)≤…≤ρ(C(n,2)～k)≤ρ(C(n,2)～(k+1))≤…≤ρ(C(n,2)～[(n+1)/2]).     

尖点形式L函数的零点密度估计(Ⅱ)

设k为一正偶数,T是充分大的正数,s=σ+it,3≤Q=T,q为一正整数,χ是模q的特征,f(z)=∞∑n=1a(n)e2πinz为Γ=SL2(z)的权为k的全纯尖点形式.设Nf(σ0,T,χ)表示函数Lf(s,χ)=∞∑n=1χ(n)a(n)n-s在带形区域k/2+(l/(log(Q2T))≤σ0≤σ≤((k+1)/2),|t|≤T内的零点个数.当k/2+1/3≤σ0≤((k+1)/2)时,由Dirichlet多项式理论得出了∑q≤Q∑χmodqNf(σ0,T,χ)的一个上界.     

关于图C_m∪P_(n-1)~+的优美性

图Ｃｍ ∪Ｐ＋ｎ－ １ 是圈Ｃｍ 与Ｐ＋ｎ－ １ 的不交并。本文证明了当①ｍ ＝ ４ｋ,ｎ ≥ｋ ＋ ２;②ｍ ＝ ４ｋ ＋ １,４ｋ － １ ≤ｎ ≤１０ｋ－ ７;③ｍ ＝ ４ｋ＋ ２,ｎ ≥４ｋ ＋ １;④ｍ ＝ ４ｋ ＋ ３,４ｋ＋ ２≤ｎ ≤１０ｋ－ ２ 时,图Ｃｍ ∪Ｐ＋ｎ－ １ 是优美的。     

一类固定系数解析函数的极值点与支撑点

摘要 设Q={f(z):f(z)=z-an+1zn+1-(∞∑k=n+2)akzk},这里an+1=c(n+2)/(n+1)(n+3),ak≥0,∞∑k=n+2k(k+2)/k+1ak≤1-c,0≤c≤1,n∈N,并且f(z)在单位圆盘△={z:| z |＜1}内解析,得到函数族Q的极值点与支撑点.     

一类斜Armendariz环A_(2k+1)(R)+RE_(u,k+u-1)的极大性

设α是环R的一个自同态,R是α-rigid环,n=2k+1≥7,那么一类上三角矩阵环An(R)+REu,k+u-1是An(R)+REu,k+u-1+REv,k+v-1的极大ā-斜Armendariz环,其中3≤u≤k,v=1,2,k+1,k+2.A5(R)是A5(R)+REv,k+v-1的极大ā-斜Armendariz环,其中v=1,2,3,4.     

关于图的圈和退化圈分拆的一个注记

设G是一个n阶图，k是满足2≤k≤n的正整数，于是得到了如下结论：如果图G的任何一对不相邻的顶点{u,v}，都满足max{dG(u)，dG(v)}≥(n-k 3)／2，则存在k个点不交的子图Hi,使得V(G)=V(H1)∪V(H2)∪…∪(Hk)，其中Hi为一个圈或一个点或一条边．     

对偶图K_(n,n)+I的循环(m_1,m_2,…,m_r)-圈分解

mi(1≤i≤r)为偶数且r∑(i=1)mi=2k(k≥1).Kn,n为偶图,I为Kn,n的一因子.证明了Kn,n+I可分解为(m1,m2,…,mr)-圈的充分必要条件为2k│n(n+1)且n为奇数.进一步,Kn,n+I可分解为循环的(m1,m2,…,mr)-圈充分必要条件为2k=n+1且n为奇数.