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.     

德摩根一致代数的度量化

我们给出了德摩根一致代数可伪度量化的一个充分必要条件。     

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.     

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 …     

模糊概念格与模糊推理

基于伽罗瓦连接,分别在交换伴随对与对合剩余格条件下,讨论了模糊概念格的四种定义形式。并证明了在对合剩余格上,对偶性成立,四种模糊算子将具有与经典意义下一致的相互关系。最后我们提出了一种基于模糊概念格的模糊推理规则,并证明了其还原性。     

Randomized algorithms for the separation of point sets and for solving quadratic programs

A randomized algorithm for finding a hyperplane separating two finite point sets in the Euclidean space ^d and a randomized algorithm for solving linearly constrained general convex quadratic problems are proposed. The expected running time of the separating algorithm isO(dd! (m + n)), wherem andn are cardinalities of sets to be separated. The expected running time of the algorithm for solving quadratic problems isO(dd! s) wheres is the number of inequality constraints. These algorithms are based on the ideas of Seidel's linear programming algorithm [6]. They are closely related to algorithms of [8], [2], and [9] and belong to an abstract class of algorithms investigated in [1]. The algorithm for solving quadratic problems has some features of the one proposed in [7].This research was done when the author was supported by the Alexander von Humboldt Foundation, Germany.On leave from the Institute of Mathematics and Mechanics, Ural Department of the Russian Academy of Sciences, 620219 Ekaterinburg, S. Kovalevskaya str. 16, Russia.     

直觉I-Fuzzy拓扑空间的杨忠道定理

以L~*-格值上Lukasiewicz蕴含算子为工具引入了直觉I-Fuzzy拓扑空间中导集概念,接着给出它的一些性质,最后证明了直觉I-Fuzzy拓扑空间中导集的杨忠道定理.