Approximation algorithms for dynamic resource allocation

We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T epochs. In each epoch, we assign to each activity a task which consumes resources, generates utility, and determines the subsequent state of the activity. We study the complexity of, and approximation algorithms for, maximizing average utility.     

FFT-based algorithms for the string matching with mismatches problem

The string matching with mismatches problem requires finding the Hamming distance between a pattern P of length m and every length m substring of text T with length n. Fischer and Paterson's FFT-based algorithm solves the problem without error in O(σnlogm), where σ is the size of the alphabet Σ [SIAM–AMS Proc. 7 (1973) 113–125]. However, this in the worst case reduces to O(nmlogm). Atallah, Chyzak and Dumas used the idea of randomly mapping the letters of the alphabet to complex roots of unity to estimate the score vector in time O(nlogm) [Algorithmica 29 (2001) 468–486]. We show that the algorithm's score variance can be substantially lowered by using a bijective mapping, and specifically to zero in the case of binary and ternary alphabets. This result is extended via alphabet remappings to deterministically solve the string matching with mismatches problem with a constant factor of 2 improvement over Fischer–Paterson's method.     

Modules over Operator Algebras and Its Module Maps

ＭｏｄｕｌｅｓｏｖｅｒＯｐｅｒａｔｏｒＡｌｇｅｂｒａｓａｎｄＩｔｓＭｏｄｕｌｅＭａｐｓＸｕＴｉａｎｚｈｏｕ（许天周）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＮａｎｊｉｎｇＵｎｉｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ，２１００９３）ＡｂｓｔｒａｃｔＬｅ...     

A Note on Topological Entropy of Maps

For a given collection of subsets of a compact metric space X which cover X,the entropies,hm(f)and hi(f),are introduced for a continuous map f of X to itseif. Also the concept of shadowing property with same end point (SPSEP for short) is introduced. The main results are,(1)H(f)≤hi(f)+hm(f)and,(2)h(f)=hm(f)whenever f has SPSEP,where h(f) is the topological entropy of f. Moreover,several corollaries are obtained.     

RANDOM EDGE can be exponential on abstract cubes

We prove that RANDOM EDGE, the simplex algorithm that always chooses a random improving edge to proceed on, can take a mildly exponential number of steps in the model of abstract objective functions (introduced by Williamson Hoke [Completely unimodal numberings of a simple polytope, Discrete Appl. Math. 20 (1988) 69-81.] and by Kalai [A simple way to tell a simple polytope from its graph, J. Combin. Theory Ser. A 49(2) (1988) 381-383.] under different names). We define an abstract objective function on the n-dimensional cube for which the algorithm, started at a random vertex, needs at least exp(const·n^1/3) steps with high probability. The best previous lower bound was quadratic. So in order for RANDOM EDGE to succeed in polynomial time, geometry must help.     

加权Herz—type Triebel—Lizorkin空间的特征及应用

当s∈ R,0,〈q, p〈∈∞,0,〈β≤∞且 max{-n/q,-nδ2/qδ1}〈a时，定义了加权Herz—type　Triebel-Lizorkin空间kq^q,pF^s β（R^n,ω1，ω2）和Kq^a,pF^sβ（R^n，ω1，ω2），并给出这些空间的一些特征及在这些空间上的Hard—Littlewood极大算子不等式．     

广义分解定理与两个不等式

本文给出了Banach空间广义分解定理的一个初等证明,并利用它来证明两个对称不等式.这是首次在Banach空间获得这样的不等式.     

GA optimization on multi-segments muffler under space constraints

Whilst the space volume of muffler in noise control system is often constrained for maintenance in practical engineering work, the maximization on muffler’s performance becomes important and essential. In this paper, a novel approach genetic algorithms (GAs) based on the principles of natural biological evolution will be used to tackle this optimization of muffler design [M. Mitchell, An Introduction to Genetic Algorithms, The MIT Press, Cambridge, MA, 1996]. Here, the shape optimization of multi-segments muffler coupled with the GA searching technique is presented. The techniques of binary genetic algorithms (BGA) together with the commercial MATLAB package [G. Lindfield, J. Penny, Numerical Method Using Matlab, second ed., Prentice Hall, Englewood Cliffs, NJ, 2000] are applied in GA searching. In addition, a numerical case of pure tone elimination with 2-5 segments on muffler is introduced and fully discussed. To achieve the best optimization in GA, several GA parameters are on trial in various values. Results show that the GA operators, including crossover mutation and elitism, are essential in accuracy. Consequently, results verify that the optimal sound transmission loss at the designed frequency of 500 Hz is exactly maximized. The GA optimization on multi-segments muffler proposed in this study surely provides a quick and correct approach.     

Pre—Separation Axioms in Fuzzifying Topology

1　 IntroductionYing[5,6 ] introduced and elementally developed so called fuzzifying topology with the semanticmethod of continuous valued L ogic.Shen[7] introduced and studied T0 -,T1-,T2 (Hausdorff) -,T3(regularity) -,T4 (normality) -separation axioms in fuzzifying topology.In [3 ]the concepts of thefamily of fuzzifying pre-open sets,fuzzifying pre-neighbourhood structure of a point and fuzzifyingpre-closure are introduced and studied.It is worth to mention that pre-separation axioms are …     

Nd:LuVO_4晶体的拉曼光谱研究

采用不同的几何配置测量了Nd:LuVO4晶体的室温拉曼光谱,根据群论对称性分类计算了该晶体的红外和拉曼活性振动模并与实验结果做了比较,指认了测定的特征谱线。测量并分析了Nd:LuVO4晶体A1g全对称类的高温拉曼光谱,讨论了拉曼频移随温度变化的关系,认为晶体的热膨胀是引起拉曼频移变化的主要原因。