On K 1,k -factorization of bipartite multigraphs

A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that （1） m ≤ kn, （2） n ≤ km, （3） km-n = kn-m ≡ 0 （mod （k^2- 1）） and （4） λ（km-n）（kn-m） ≡ 0 （mod k（k- 1）（k^2 - 1）（m ＋ n））.     

A variation of a conjecture due to Erdös and Sós

Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.     

关于完全t部图K(n1,n2,…,nt)的色唯一性

设P（G，λ）是图G的色多项式，如果对任意使P（G，λ）=P（H，λ）的图H都与G同构，则称G是色唯一图。这里通过比较图的特征子图的个数，讨论了由Koh和Teo在文献[1]中提出的问题（若｜ni-nj｜≤2，1≤i，j≤t且min{n1，n2，…，nt}充分大，K（n1，n2，…，nt）是否为色唯一图？）。证明了，若｜ni—nj｜≤2且t↑∑↑i=1 ni〉t^2/2＋t√t-1，则K（n1，n2，…，nt）是色唯一图；若αi=0或k，t↑∑↑i=1 n＋αi〉t^2k^2/8＋｜tk｜/2√t-1，则K（n＋α1，n＋α2，…，n＋αt）是色唯一图。其条件比文献[4]中的条件较好一些。     

关于带权的Hardy-Hilbert不等式中的一个上确界

本文引入了一个形如π/sin-Or（n）/n的权系数，其中Or（n）＞0（r＞1）．建立了带权的Hardy-Hilbert不等式，给出了Or（n）的下确界与上确界．特别当r=2时，证明了λ=1．4603545…是O2（n）的上确界，解决了文[2][6]中所提出的几个问题．     

导出1^3＋2^3＋3^3…＋n^3的公式的一种方法

笔者曾在《中学生数学》2002年第5期（上）发表了《导出1^2＋2^2＋…＋n^2的公式的一种方法》的文章,主要阐述用“全等三角形”数阵并进行“二维”变化进行叠加,得到n∑k=1k^2结论的方法．     

奇异k紧整数的无限族

设n，s1，s2是3个正整数，使得s1〈s2〈n，gcd（n．s1，s2）=1，G（n；s1，s2）是n个结点的步长为s1和s2的双环网，d（n；s1，s2）是其直径．设d（n）=min{d（n；s1，s2）│s1〈s2〈n}，d1（n）=min{d（n；1，s）│1〈s〈n}．已知d1（n）≥d（n）≥[√3n]-2=lb（n）．若d（n；s1，s2）=d（n）=lb（n）＋k，k≥0，则称双环网G（n；s1，s2）是k紧优双环网．若d1（n）〉d（n）=lb（n）＋k，则n称为奇异k紧整数．本文给出构造奇异k紧整数无限族的方法，并对于k=1，2．…，20．构造出这样的无限族．     

NA序列中心极限定理的收敛速度

本文对NA（NegativelyAssociated）序列建立了中心极限定理的一致收敛速度，只要其三阶矩有限及描述NA序列协方差结构的一个系数u（n）被负指数序列所控制，而无需平稳性便获得了其收敛速度O（n(-1/2)logn）。     

关于S\''{a}rk\"{o}zy和S\''{o}s问题的一个注记

令$k,\ell \geq 2$是正整数.令$A$是无限非负整数的集合.对$n\in \mathbb{N}$, 令$r_{1,k,\ldots,k^{\ell-1}}(A, n)$表示方程$n=a_0+ka_1+\cdots +k^{\ell-1}a_{\ell-1}$, $a_0, \ldots, a_{\ell-1}\in A$解的个数. 在本文中, 我们证明了对所有$n\geq 0$, $r_{1,k,\ldots,k^{\ell-1}}(A, n)=1$当且仅当$A$是$k^\ell$进制展开中数位小于$k$的所有非负整数的集合. 这个结果部分回答了S\''{a}rk\"{o}zy and S\''{o}s关于多维线性型表示的一个问题.     

一种最佳平方逼近的C^n＋k次多项式插值方法

设节点数据{xj,yj}j=0^n来自函数y=f(x),Pn k(x)为满足插值条件Pn k(xj)=yj,(j=0,1, …,n）的n k次多项式插值,In(x)为分段线性插值多项式。本在范数‖Pn(x)-f(x)‖2或‖Pn(x)-In(x)‖）2意义下得出了一种最佳平方逼近的C^n k次多项式插值Pn k^*(x),并且证明了Pn k^*(x)的存在唯一性及其相关性质。实践表明该方法有效地抑制了Runge现象的产生。     

二阶数乘问题的一个最优算法

研究一个有趣的组合优化问题——二阶数乘问题.问题描述如下：给定n≥2个正整数a_1,a_2,…,a_n,设π为{1,2,…,n}的一个置换,表示该问题的一个解,试图找到一个置换π以至∑_（i=1）~n a_（π_i）a_（π_（i＋1））最小,在这里π_（n＋1）=π_1.给出了一个算法复杂度为O（n log n）的最优算法.     

Minimizing Completion Time Variance with Compressible Processing Times

We introduce a new formulation of the standard completion time variance (CTV) problem with n jobs and one machine, in which the job sequence and the processing times of the jobs are all decision variables. The processing time of job i (i=1, ,n) can be compressed by an amount within [l_i, u_i], which however will incur a compression cost. The compression cost is a general convex non-decreasing function of the amount of the job processing time compressed. The objective is to minimize a weighted combination of the completion time variance and the total compression cost. We show that, under an agreeable condition on the bounds of the processing time compressions, a pseudo-polynomial algorithm can be derived to find an optimal solution for the problem. Based on the pseudo-polynomial time algorithm, two heuristic algorithms H1 and H2 are proposed for the general problem. The relative errors of both heuristic algorithms are guaranteed to be no more than , where is a measure of deviation from the agreeable condition. While H1 can find an optimal solution for the agreeable problem, H2 is dominant for solving the general problem. We also derive a tight lower bound for the optimal solution of the general problem. The performance of H2 is evaluated by complete enumeration for small n, and by comparison with this tight lower bound for large n. Computational results (with n up to 80) are reported, which show that the heuristic algorithm H2 in general can efficiently yield near optimal solutions, when n is large.     

一类推广的干摩擦问题周期解的存在性

为了得到干摩擦问题存在周期解的判断方法,利用微分包含理论对系统+k~2x+μSngp(t)+T(t)a.e.进行了讨论.在周期外力p(t)周期等于固有周期2π/R的情形下得到了周期解存在的充要条件,在周期外力p(t)周期不等于固有周期整数倍2nπ/R的情形下得到了周期解存在的充分条件.     

主次指标为最小化总完工时间和存储费用的带有准备时间的单机分批排序问题

In this paper, the single machine scheduling problem with release dates and two hierarchical criteria is discussed. The first criterion is to minimize makespan, and the second criterion is to minimize stocking cost. We show that this problem is strongly NP-hard. We also give an O(n2) time algorithm for the special case that all stocking costs of jobs in unit time are 1.     

An accelerated augmented Lagrangian method for linearly constrained convex programming with the rate of convergence O(1/k~2)

In this paper, we propose and analyze an accelerated augmented Lagrangian method(denoted by AALM) for solving the linearly constrained convex programming. We show that the convergence rate of AALM is O(1/k~2) while the convergence rate of the classical augmented Lagrangian method(ALM) is O(1/k). Numerical experiments on the linearly constrained l_1-l_2minimization problem are presented to demonstrate the effectiveness of AALM.     

關於k進表示法的一個問题

<正> §1.設k>1是一個固定的正整數,則每一個正整數x都可以唯一地表成 x=a_1k~n1+a_2k~n2+…+a_1k~nt,其中n_1>n_2>…>n_t≥0都是整數;a_1,…,a_t也都是正整數且≤k-1.我們令,並令.在k=2的情况,文[1]的作者們證明了     

Geodesic Ham-Sandwich Cuts

Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n = m + r + b. A ham-sandwich geodesic is a shortest path in P between two points on the boundary of P that simultaneously bisects the red points and the blue points. We present an O(n log k)-time algorithm for finding a ham-sandwich geodesic. We also show that this algorithm is optimal in the algebraic computation tree model when parameterizing the running time with respect to n and k.     

一类源自可加、二次、三次和四次映射的泛函方程的模糊稳定性

在模糊Banach空间中研究了混合泛函方程f(x+ky)+f(x-ky)=k~2f(x+y)+k~2f(x-y)+2(1-k~2)f(x)+(k~2(k~2-1))/12(f(2y)-4f(y))的Hyers-Ulam稳定性,这里k>1是固定的一个整数,f(y)=f(y)+f(-y).     

基因组重组问题的一个更快算法

寻找一个基因组(源基因组)转化成另一个基因组(目标基因组)所需最少数目移位和翻转的问题,称为基因组重组问题.此问题的“瓶颈”在于寻找源基因组的一个最优“联接”;若源基因组和目标基因组是“共尾”的,Hannenhalli和Pevzner给出一个O(n2)算法得到源基因组的一个最优“联接”,本文将此算法复杂性将低到O(n),其中n为基因组中所含基因的个数.从而由Eric.T和MarieFrance的结果得到求“共尾”标号基因组间重组序列的一个O(nnlogn)算法.     

二维非线性抛物型微分方程的一个三层差分格式

1.引言 对于非线性抛物型微分方程第一边值问题: ?其中Ω:{0≤x,y≤1},0相似文献   

Matching parentheses in parallel

Parallel algorithms for evaluating arithmetic expressions generally assume the computation tree form to be at hand. The computation tree form can be generated within the same resource bounds as the parenthesis matching problem can be solved. We provide a new cost optimal parallel algorithm for the latter problem, which runs in time O(log n) using O(n/log n) processors on an . We also prove that the algorithm is the fastest possible independently of the number of processors available.