单机排序问题的数学规划表示

本文把单机排序问题1||∑wjCj表述成一个二次规划,并把不带权的问题1||∑Cj进一步转化成指派问题,从而用指派问题的匈牙利算法证明SPT序是问题1||∑Cj的最优解,这个结论似乎很平凡,但对于用数学规划来研究排序问题是一个很有意义的进展,这为我们用二次规划和半定规划来研究NP困难的排序问题的近似算法打下基础。     

资源有限的加权总完工时间单机排序问题

本讨论资源有限的加权总工时间单机排序问题，对现在仍为OPEN问题1｜pj=bj-ajuj，∑uj≤U｜∑wjCj给出了一个有关最优解中最优资源分配的重要性质，并利用该性质分别给出了三种情况bj=b,wj=w,aj=a；bj=b,wj=w,uj=u；aj=a,wj=w,uj=u的最优算法。     

一类扩展线性规划问题及其算法

研究扩展线性规划问题（Ⅰ）ｍｉｎｚ＝∑ｎｊ＝１ｃｊ｜ｘｊ｜，ｓ．ｔ．Ａｘ＝ｂ证明了它与一类线性规划问题的等价性，给出其不扩展单纯形表的单纯形算法     

工件带到达时间的两阶段柔性流水作业的近似算法

研究了工件带到时间的两阶段柔性流水作业的排序问题,基于求解流水作业和平行机问题的算法思想,提出两个相应的近似算法H(R)和H(MR(?)),证明了这两个算法的最坏情况性能比分别为3-1/m和2/5-1/m,讨论了界的紧性,并利用数值模拟以分析算法与最优值的近似性能比.     

找回遗漏的解

题目1已知函数f（x）=｜x＋1｜＋｜x＋2｜＋…＋｜x＋2011｜＋｜x-1｜＋｜x-2｜＋…＋｜x-2011｜（x∈R）,且f（a^2-3a＋2）=f（a-1）,则满足条件的所有整数a的和是_____．     

稠密平分子图与表压缩问题的近似算法

给出两个NP问题(稠密平分子图和表压缩)的改进的近似算法. 基于半定规划(SDP)松弛和巧妙的舍入技巧, 首先给出稠密平分子图问题(DSP)的0.5982-近似算法, 表压缩问题(TCP)的0.5970-近似算法. 然后, 通过增加三角不等式得到更紧的SDP松弛, 把前面的比值分别改进到0.6243和0.6708. 针对TCP得到的结果改进了简单贪婪算法的0.5近似比, 因此回答了Anderson提出的未解决问题.     

平方度量的k层设施选址问题的近似算法

本文中,我们研究平方度量的k层设施选址问题,该问题中设施分为k层,每个顾客都要连接到位于不同层上的k个设施,顾客与设施以及设施与设施之间的距离是平方度量的.目标是使得开设费用与连接费用之和最小.基于线性规划舍入技巧,我们给出了9-近似算法.进一步,我们研究了平方度量的k层软容量设施选址问题,并给出了线性规划舍入12.2216-近似算法.     

排序问题P2|prmp|Cmax在中断—重复模型下的调度

对于传统的中断-恢复模型下的P2｜prmp｜Cmax问题，已有最优调度规则。但中断-恢复模型并不是一般意义下的中断模型。在某些情况下，被中断的任务不能被简单的恢复加工，而是在该任务被重新加工之前必须有一定的延迟时间。延迟可能是该项任务的一部分（或者是全部）需要返工的时间。本文在研究了排序问题P2｜prmp｜Cmax在中断-重复模型下的调度，指出对于选择哪一个任务被中断的问题是NP—hard的；而对于如何处理被中断的任务的问题，指出当被中断任务的最初被加工时间由Xj增加为Xj＋△xj=Xj/（1-1/2aj）时，可使得两台处理机的时间表长相等，从而达到最优。最优时间表长为：Cmax^＊=1/2n∑j=1pj＋ajxj/（2-aj）。最后给出了在中断-重复模型下的调度规则。     

具临界Sobolev-Hardy指数的半线性椭圆方程的非平凡解

本文研究了如下问题：-div（｜x｜β△u）=｜x｜^a｜u｜^2（α,β）-2u＋λ｜x｜σ｜u｜^q-2,x∈Ω,u=0,x∈δΩ,这里Ω∪→R^N是有界光滑区域且0∈Ω，2（α，β）=2（N＋α）/N＋β-2，运用Sobolev-Hardy不等式和山路几何，证明了在一定的条件下方程至少存在一个非平凡解。     

移动传感器网络中的最大价值路径扫描覆盖算法

扫描覆盖是当前移动传感器网络的一个重要覆盖技术,其主要通过规划移动传感器的巡逻路径对事件兴趣点（Points of Interest,POI）进行定期监测,从而以相对于普通覆盖方案更低廉的成本实现对POI监控．研究最大价值路径扫描覆盖,即使用移动传感器扫描覆盖分布在一条路径上的POI集合,使得被覆盖POI的价值总和达到最大．首先设计了一个基于线性规划随机取整的近似算法,通过将问题松弛并刻画为一个线性规划,然后对线性规划最优解取整得到一个扫描覆盖方案．该算法可在O（mn^3.5L）时间内求解,并具有可证明的近似比1-1/e．其次,通过扩展基于贪心策略的集合覆盖算法,设计了一个时间复杂度为O（m²n²）的贪心算法,其主要思想为循环选取一个单位巡逻范围覆盖POI价值最大的传感器．为优化运行时间,基于MVSCP问题的特殊结构将算法时间进一步改进至O（m log m+mn²）．最后,通过仿真实验分析所设计算法的实际性能.实验结果表明,线性规划随机取整算法运行时间低至整数规划算法的百分之一,但其所求解的质量只略低于整数规划算法;改进的贪心算法虽然不具有可证明的近似比,但其实际所求解的质量并不弱于线性规划随机取整算法,并且具有三者中最佳的运行时间．     

RECENT PROGRESS ON SPHERICAL HARMONIC APPROXIMATION MADE BY BNU RESEARCH GROUP ——In memory of Professor Sun Yongsheng

As early as in 1990, Professor Sun Yongsheng, suggested his students at Beijing Normal University to consider research problems on the unit sphere. Under his guidance and encouragement his students started the research on spherical harmonic analysis and approximation. In this paper, we incompletely introduce the main achievements in this area obtained by our group and relative researchers during recent 5 years （2001-2005）. The main topics are： convergence of Cesaro summability, a.e. and strong summability of Fourier-Laplace series; smoothness and K-functionals; Kolmogorov and linear widths.     

On a class of self-similar processes with stationary increments in higher order Wiener chaoses

We study a class of self-similar processes with stationary increments belonging to higher order Wiener chaoses which are similar to Hermite processes. We obtain an almost sure wavelet-like expansion of these processes. This allows us to compute the pointwise and local Hölder regularity of sample paths and to analyse their behaviour at infinity. We also provide some results on the Hausdorff dimension of the range and graphs of multidimensional anisotropic self-similar processes with stationary increments defined by multiple Wiener–Itô integrals.     

On a class of Riemann surfaces

It is considered the class of Riemann surfaces with dimT1 = 0, where T1 is a subclass of exact harmonic forms which is one of the factors in the orthogonal decomposition of the spaceΩH of harmonic forms of the surface, namely The surfaces in the class OHD and the class of planar surfaces satisfy dimT1 = 0. A.Pfluger posed the question whether there might exist other surfaces outside those two classes. Here it is shown that in the case of finite genus g, we should look for a surface S with dimT1 = 0 among the surfaces of the form Sg\K , where Sg is a closed surface of genus g and K a compact set of positive harmonic measure with perfect components and very irregular boundary.     

A REPRESENTATION FORMULA RELATED TO SCHR(O)DINGER OPERATORS

Schr(o)dinger operator is a central subject in the mathematical study of quantum mechanics.Consider the Schrodinger operator H = -△ V on R, where △ = d2/dx2 and the potential function V is real valued. In Fourier analysis, it is well-known that a square integrable function admits an expansion with exponentials as eigenfunctions of -△. A natural conjecture is that an L2 function admits a similar expansion in terms of "eigenfunctions" of H, a perturbation of the Laplacian (see [7], Ch. Ⅺ and the notes), under certain condition on V.     

Boundedness for commutators of multipliers on Hardy type spaces

In this paper, we study the commutators generalized by multipliers and a BMO function. Under some assumptions, we establish its boundedness properties from certain atomic Hardy space Hb^p（R^n） into the Lebesgue space L^p with p 〈 1.     

A unified approach to certain problems of best local approximation

In this paper we study best local quasi-rational approximation and best local approximation from finite dimensional subspaces of vectorial functions of several variables. Our approach extends and unifies several problems concerning best local multi-point approximation in different norms.     

THE 8~(th) INTERNATIONAL CONGRESS ON INDUSTRIAL AND APPLIED MATHEMATICS

<正>August 10-14,2015Beijing,ChinaThe International Congress on Industrial and Applied Mathematics(ICIAM)is the premier international congress in the field of applied mathematics held every four years under the auspices of the International Council for Industrial and Applied Mathematics.From August 10 to 14,2015,mathematicians,scientists     

Towards Excellence in Science Chinese Academy of Sciences

<正>May 26,2014,Beijing Science is a human enterprise in the pursuit of knowledge.The scientific revolution that occurred in the 17th Century initiated the advances of modern science.The scientific knowledge system created by