箱子是在线到达的带核元变尺寸装箱问题

本文考虑了一类箱子在线到达的带核元变尺寸装箱问题．假定箱子的尺寸可以是不同的．箱子是在线到达的，仅当箱子到达后其尺寸才知道．给定一个带有核元的物件表，目标是要将表中元素装入到达的箱子中，使得所用的箱子总长最小．我们首先证明了该问题是强NP—Hard，其次分析了经典算法NF(D)和FF(D)的性能界，指出NF(D)和FF(D)算法的性能界可以任意大．最后我们给出了相应的修改算法MNF(D)和MFF(D)，证明了它们的性能界都是3，此界是紧的．     

球超图最大边数的一个下界

设V={v_1,v_2,…,v_n}是一个有限集,E={e_1,e_2,…e_m}是V的非空子集的一个族,满足则称H=(V,E(是一个超图[1],V的元素称为H的顶点,E的元素称为H的边。n称为H的阶。若E中的元素两两不相同,则H称为是简单的。若V是k维欧氏空间ε_k中的点集,且有m个k维闭球B_1,B_2,…。B_m,使B_i中恰含e_1中的点,即     

货物尺寸相同的2维装箱问题的等价类(英文)

在生产与储运领域,把小长方体货物（盒子）装入大长方体箱子是一项重要的工作.本文涉及的问题是:把相同尺寸（a×b×c）的盒子装到一个箱子X×Y×Z中,使所装入箱子的盒子数量为最大.由于某些条件的限止,有时要求货物只能按一个重力方向进行装箱,从而使装箱问题变为把尺寸相同的2维盒子（a×b）填装到一个2维箱子X×Y中.本文讨论当盒子尺寸（a×b包括 b×a）给定,箱子尺寸充分大时,在本文所给的等价意义下,共有多少种互不等价的箱子X×Y.     

货物尺寸相同的2维装箱问题的等价类

在生产与储运领域,把小长方体货物(盒子)装入大长方体箱子是一项重要的工作.本文涉及的问题是把相同尺寸(a×b×c)的盒子装到一个箱子X×Y×Z中,使所装入箱子的盒子数量为最大.由于某些条件的限止,有时要求货物只能按一个重力方向进行装箱,从而使装箱问题变为把尺寸相同的2维盒子(a×b)填装到一个2维箱子X ×Y中.本文讨论当盒子尺寸(a×b包括b×a)给定,箱子尺寸充分大时,在本文所给的等价意义下,共有多少种互不等价的箱子X×Y.     

COMPLETELY POSITIVE MAPS AND-ISOMORPHISM OF C-ALGEBRAS

Let A,B be unital C~*-algebras.X_A={|are all completely positive linear maps from M_n(C)to A with ‖a‖≤1}.(a=((e_(11))…(e_(1n)……(e_(n1))…(e_(nn))),where{e_(iy)}is the matrix unit of M_n(C).)Let a be the natural action of SU(n)on M_n(C).For n≥3,if Φis an a-invariant affine isomorphism between X_A and X_B,Φ(0)=0,then A and B are~*-isomorphic.In this paper a counter example is given for the case n=2.     

物品大小不超过1/2的一维在线装箱模型研究

研究主要针对所有装入物品大小上限为1/2时的一维装箱问题模型展开,根据物品尺寸大小划分的思想,提出一种新的一维在线装箱算法.本模型中,物品在线到来,对即将到来的物品信息及物品数量未知,算法执行过程中,首先根据物品尺寸大小将物品划分成7大类,再根据欲先设定的packing规则,将对应类物品放入对应类型箱子中,任何时刻,算法最多打开7个箱子.算法设计过程中,不再需要额外的空间存储物品,物品一旦装入箱子不允许取出重装,箱子关闭后不允许再打开装其他物品.最后,通过详细的分析计算,验证出本算法能获得1.4236的渐近竞争比.同时通过实例构建得出问题新的下界为1.4231,将上下界之间的缝隙缩小至0.0005.     

从(?)-同调球到(?)-紧致Hausdorff空间的(?)映射问题的一个定理

§0.序言及主要结果的陈述 在1947年,B.Knaster曾提出下列推测: 给定从(m n-2)-维的球面S~(m n-2)到m-维欧氏空间R~m的连续映射f:S~(m n-2)→R~m以及n个不同的点e_1,…,e_n∈S~(m n-2),是否存在一个旋转r,使得f(re_1)=…=f(re_n)? 对于这一问题已有不少人研究过:例如, 当m=1,n=3 且e_1,e_2,e_3(作为向量)互相垂直时,Kakutani给出了证明(我们称之为Kakutani定理)…。     

一类带多重核元集在线装箱问题

本文讨论了一类在线变尺寸装箱问题,假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物品表及其上的核元关系图.我们的目标是要将表中元素装入到达的箱子中,保证任何箱子所装物品不互为核元,即所装物品对应的点所导出的子图是个空图,并使得所用的箱子总长最小.我们证明了该问题是NPHard的,并给出了基于图的点染色、图的团分解和基于背包问题的近似算法,给出了算法的时间复杂度和性能界.     

实 Clifford 分析中的一个边值问题

考虑以 e_A=e_(α1)…e_(αh)(A={α_1,α_2,…,α_h)(?){1,2,3,…,n),1≤α_1<α_2<…<α_h≤n)为基底元素的实 Clifford 代数 A_n(R),其中 e_1=1,e_k~2=-1(k=2,3,4,…,n),e_ke_m e_me_k=0(k≠m,k,m=2,3,4,…,n).并用 V_n 表示由向量组 e_1,e_2,…,e_n 所张成的 A_n(R)的子空间,V_n 中元素为 x=(?)x_ke_k,A_n(R)中的     

带参量的非合作装箱博弈

带参量的非合作装箱博弈是指:每个物品的尺寸都介于0和参量x(0相似文献   

两个和式的求法

文[1]给出了以下问题及其答案:问题有一个楼梯共有n级,如果规定每一步只能走1级或者2级,那么要登上第n级楼梯共有多少种不同的走法?答案:当n为奇数时,走法有C1n 12 C3n 23 C5n2 5 … Cnn n2种,当n为偶数时,走法有C02n C2n2 2 C4n 42 … Cnn n2种.下面我们来求出这两个和式的结果.对一切k∈N*,记Ak=C1k C3k 1 C5k 2 … C22kk--11,则A1=1,A2=3,A3=8,….记Bk=C0k C2k 1 C4k 2 … C22kk--12 C22kk,则B1=2,B2=5,B3=13,….显然,原问题的答案分别为An2 1和B2n.定理1Ak Bk=Ak 1.(用Cnm Cnm 1=Cnm 11可证)定理2Ak 2=3Ak 1-Ak.证明3A…     

无限循环群被有限生成Abel群的中心扩张

设G是无限循环群被有限生成Abel群的中心扩张,T是G的中心ζG的挠子群.如果T的阶与ζG/(G'⊕T)的挠子群的阶互素,那么群G可分解为G=S×F×T,其中S= 这里d_i都是正整数,满足d_1|d_2|…|d_r,F是秩为s的自由Abel群,T是有限Abel群,T=Z_(e_1)⊕Z_(e_2)⊕…⊕Z_e_t,e_11,满足e_1|e_2|…|e_t,并且(d_1,e_t)=1.进一步,(d_1,d_2,…,d_T;s;e_1,e_2,…,e_t)是群G的同构不变量,即若群H也是无限循环群被有限生成Abel群的中心扩张,T_H是ζH的挠子群.如果T_H的阶与ζH/(H'⊕T_H)的挠子群的阶互索,那么G同构于H的充要条件是它们有相同的不变量.显然,这个结果涵盖了有限生成Abel群的结构定理.     

特殊集上素变数方程的解

令n=e_0+e_12+…+e_k2~k,其中e_j=0,1(j=0,…,k)表示自然数n的二进制展开式,N_0表示二进制展开式中项数为偶数的自然数的集合.分别给出了这个特殊集上素变数方程p_1+p_2+p_3~k=N和p_1+p_2~2+p_3~2+p_4~2=N解的个数的渐近公式.     

关于调和级数部分和的估计

本文利用 Bernoulli 数给出可以精确到任意 O(1/n~(2k))阶的 Euler 公式,即对任意自然数 k,总有(?)1/m=C+(?)nn+1/(2n)-((?)B_(2(?)))/(2i)·1/(n~(2(?)))+O(1/(n~(2(k+1)))其中,B_(2(?))(i=1,2,3,…)为 Bernoulli 数,C 为 Euler 常数.     

一个单形不等式等号成立的举例

关于猜测:“自E~n中的单形B_1B_2…B_(n+1)内的任意一点M作各面的垂线,分别交各面于C_1,C_2,…C_(n+1),则 |V_((c_1c_2)…c_(n+1))|≤1/n~n|V((B_1B_2…B(n+1))|式中等号当仅且当M是单形B_1B_2…B_(n+1)的外接球球心时成立。”文作了颇精妙的证明并指出:“当n≥3时,一般地,猜测中取等号的条件是不成立的”,这预示单形该性质有异化的情况。为了使其发生变化的情况有所具体表现,我们通过对     

分枝与定界(Branch and Bound)方法简介

1引言不少组合最优化问题可以归结为下面的形式:max f (x)或min f(x),这里s是一个有限集合。让我们看几个例子。[例1]分配问题(Assignment Problem,以下简称为AP)设有n个人A_1,A_2,…,A_n,另外有n件工作B_1,B_2m,…;B_n,又设A_i做工作B_j可以生产的价值为C_(ij),现在要分配每一个人A_i做一件工作B_j,规定每一个人都恰好     

微积分在组合数求和证明中的应用

关于微积分的应用,我们知道的已经很多,如求极值问题、几何应用、物理应用,以及利用微积分解决有关级数的求和问题等,但利用微积分解决有关组合数的和的计算与证明却比较少见.本文想通过几个例子,一方面丰富解决组合数求和及证明这类问题的方法,另一方面可让大学生朋友进一步了解数学这一工具的重要性和应用的广泛性.例1　证明:C1n 2C2n 3C3n … nCnn=n2n-1C1n-2C2n 3C3n-… (-1)n-1nCnn=0证明　因为(1 x)n=1 C1nx C2nx2 … Cnnxn,两边对x求微分,有n(1 x)n-1=C1n 2C2nx 3C3nx2 … nCnnxn-1.令x=1,则有C1n 2C2nx 3C3nx2 … nCnn=n2n-…     

全脐子流形的特征

设 M 是浸入 n p 维常曲率黎曼流形(?)中的 n 维子流形。选取(?)中的一个局部标准正交标架场 e_1,…,e_(n p),使当其限制到 M 上时,e_1,…,e_n 是 M 的切向量场。我们约定下列指标的取值范围:     

Grassmann代数与行列式

本文应用超复数系上的Grassmann代数来建立行列式理论。 设e_1,e_2,…,e_n是域P上n维线性空间V_n的一个基底,定义基底向量的乘法为 e_ie_j=-e_je_i,e_i~2=θ (i≠j,i,j=1,2,…,n)(1)θ是V_n的零向量,并且基底的乘法满足结合律,     

例谈分球入箱问题的解法

将n个球放入k个箱子中,有多少种不同的放法?此类问题我们称之为分球入箱问题。它含有多种情形：n个球是否相同?k个箱子有无差异?箱子允许空否?解决此类问题的关键是分辨在什么情况下与顺序有关,在什么情况下与顺序无关。现举例说明如下。例1 将7个相同的小球,放入4个相同的箱子中。 (1)每个箱子中至少有一个小球(箱子不空)有多少种不同的放法? (2)若箱子允许空又有多少种不同的放法? 分析箱子相同时不需考虑箱子的顺序,球相同也无需考虑球的差别,只要考虑各个箱子中放入小球的多少。可用穷举法求解。解 (1)箱子不空有3种放法：