Potts models with magnetic field: Arithmetic,geometry, and computation

We give a sheaf theoretic interpretation of Potts models with external magnetic field, in terms of constructible sheaves and their Euler characteristics. We show that the polynomial countability question for the hypersurfaces defined by the vanishing of the partition function is affected by changes in the magnetic field: elementary examples suffice to see non-polynomially countable cases that become polynomially countable after a perturbation of the magnetic field. The same recursive formula for the Grothendieck classes, under edge-doubling operations, holds as in the case without magnetic field, but the closed formulae for specific examples like banana graphs differ in the presence of magnetic field. We give examples of computation of the Euler characteristic with compact support, for the set of real zeros, and find a similar exponential growth with the size of the graph. This can be viewed as a measure of topological and algorithmic complexity. We also consider the computational complexity question for evaluations of the polynomial, and show both tractable and NP-hard examples, using dynamic programming.     

Frequency Insertion Strategy for Channel Assignment Problem

This paper presents a new heuristic method for quickly finding a good feasible solution to the channel assignment problem (CAP). Like many other greedy-type heuristics for CAP, the proposed method also assigns a frequency to a call, one at a time. Hence, the method requires computational time that increases only linear to the number of calls. However, what distinguishes the method from others is that it starts with a narrow enough frequency band so as to provoke violations of constraints that we need to comply with in order to avoid radio interference. Each violation is then resolved by inserting frequencies at the most appropriate positions so that the band of frequencies expands minimally. An extensive computational experiment using a set of randomly generated problems as well as the Philadelphia benchmark instances shows that the proposed method perform statistically better than existing methods of its kind and even yields optimum solutions to most of Philadelphia benchmark instances among which two cases are reported for the first time ever, in this paper. Won-Young Shin was born in Busan, Korea in 1978. He received B.S. in industrial engineering from Pohang University of Science and Technology (POSTECH) in 2001 and M.S in operation research and applied statistics from POSTECH in 2003. Since 2003 he has been a researcher of Agency for Defense Development (ADD) in Korea. He is interested in optimization of communication system and applied statistics. Soo Y. Chang is an associate professor in the Department of Industrial Engineering at Pohang University of Science and Technology (POSTECH), Pohang, Korea. He teaches linear programming, discrete optimization, network flows and operations research courses. His research interests include mathematical programming and scheduling. He has published in several journals including Discrete Applied Mathematics, Computers and Mathematics with Application, IIE Transactions, International Journal of Production Research, and so on. He is a member of Korean IIE, and ORMSS. Jaewook Lee is an assistant professor in the Department of Industrial Engineering at Pohang University of Science and Technology (POSTECH), Pohang, Korea. He received the B.S. degree in mathematics with honors from Seoul National University, and the Ph.D. degree from Cornell University in applied mathematics in 1993 and 1999, respectively. He is currently an assistant professor in the department of industrial engineering at the Pohang University of Science and Technology (POSTECH). His research interests include nonlinear systems, neural networks, nonlinear optimization, and their applications to data mining and financial engineering. Chi-Hyuck Jun was born in Seoul, Korea in 1954. He received B.S. in mineral and petroleum engineering from Seoul National University in 1977, M.S. in industrial engineering from Korea Advanced Institute of Science and Technology in 1979 and Ph.D. in operations research from University of California, Berkeley, in 1986. Since 1987 he has been with the department of industrial engineering, Pohang University of Science and Technology (POSTECH) and he is now a professor and the department head. He is interested in performance analysis of communication and production systems. He has published in several journals including IIE Transactions, IEEE Transactions, Queueing Systems and Chemometrics and Intelligent Laboratory Systems. He is a member of IEEE, INFORMS and ASQ.     

Fast handoff with reducing waste rate approach for wireless resources management in UMTS mobile networks

3G Wideband CDMA systems adopt the Orthogonal Variable Spreading Factor code tree as the channelization codes management for achieving high data rate transmission in personal multimedia communications. It assigns a single channelization code for each accepted connection. Nevertheless, it wastes the system capacity when the required rate is not powers of two of the basic rate. One good solution is to assign multiple codes for each accepted connection but it causes two inevitable drawbacks: long handoff delay and new call setup delay due to high complexity of processing with multiple channelization codes, and high cost of using more number of rake combiners. Especially, long handoff delay may result in more call dropping probability and higher Grade of Service, which will degrade significantly the utilization and revenue of the 3G cellular systems. Therefore, we propose herein an adaptive efficient codes determination algorithm based on the Markov Decision Process analysis approach to reduce the waste rate and reassignments significantly while providing fast handoff. Numerical results demonstrate that the proposed approach yields several advantages, including the lowest GOS, the least waste rate, and the least number of reassignments. Meanwhile, the optimal number of rake combiners is also analyzed in this paper. This research was supported in part by the National Science Council of Taiwan, ROC, under contract NSC-93-2213-E-324-018.     

准移动闭塞系统的元胞自动机模型及列车延迟传播规律的研究

在NaSch模型的基础上，针对铁路交通的特点提出一种用于模拟准移动闭塞系统的元胞自动机模型.应用该模型模拟了准移动闭塞系统列车延迟传播的交通现象，分析了准移动闭塞系统中的轨道定位单元长度、发车时间间隔、初始延迟时间等因素对列车延迟传播的影响. 关键词： 元胞自动机 交通流 准移动闭塞     

Space-Time Directional Lyapunov Exponents for Cellular Automata

Space-time directional Lyapunov exponents are introduced. They describe the maximal velocity of propagation to the right or to the left of fronts of perturbations in a frame moving with a given velocity. The continuity of these exponents as function of the velocity and an inequality relating them to the directional entropy is proved.     

Bandwidth Adaptation Algorithms for Adaptive Multimedia Services in Mobile Cellular Networks

The fluctuation of available link bandwidth in mobilecellular networks motivates the study of adaptive multimediaservices, where the bandwidth of an ongoing multimedia call can bedynamically adjusted. We analyze the diverse objectives of theadaptive multimedia framework and propose two bandwidth adaptationalgorithms (BAAs) that can satisfy these objectives. The firstalgorithm, BAA-RA, takes into consideration revenue and``anti-adaptation' where anti-adaptation means that a user feelsuncomfortable whenever the bandwidth of the user's call ischanged. This algorithm achieves near-optimal total revenue withmuch less complexity compared to an optimal BAA. The secondalgorithm, BAA-RF, considers revenue and fairness, and aims at themaximum revenue generation while satisfying the fairnessconstraint defined herein. Comprehensive simulation experimentsshow that the difference of the total revenue of BAA-RA and thatof an optimal BAA is negligible. Also, numerical results revealthat there is a conflicting relationship between anti-adaptationand fairness.     

与HBV X蛋白相互作用的细胞蛋白的筛选及其鉴定

参考GenBank核苷酸序列库中的HBV的核苷酸序列设计合成了一对对应于HBx基因的引物，从原发性肝癌(hepatocellular carcinoma，HCC)患者的血清中提取HBV基因组DNA作为模板，扩增HBx编码区并测定了核苷酸序列．将该编码区克隆到酵母双杂交系统的诱饵蛋白表达载体pGBKT7中，转入酵母细胞AH109，进行表型鉴定．然后通过Mating实验从已制备好用于酵母双杂交系统的肝cDNA表达文库中筛选与HBx相互作用的细胞蛋白，并用体外免疫共沉淀实验进一步验证．研究表明，分离得到的与HBx基因编码的蛋白相互作用的4种新的细胞蛋白，分别是醛缩酶B、C8α亚基、一种丝氨酸蛋白酶Hepsin和一种未知蛋白．     

Ergodic properties and thermodynamic behavior of elementary reversible cellular automata. I. Basic properties

This is the first part of a series devoted to the study of thermodynamic behavior of large dynamical systems with the use of a family of fully-discrete and conservative models named elementary reversible cellular automata (ERCAs). In this paper, basic properties such as conservation laws and phase space structure are investigated in preparation for the later studies. ERCAs are a family of one-dimensional reversible cellular automata having two Boolean variables on each site. Reflection and Boolean conjugation symmetries divide them into 88 equivalence classes. For each rule, additive conserved quantities written in a certain form are regarded as a kind of energy, if they exist. By the aid of the discreteness of the variables, every ERCA satisfies the Liouville theorem or the preservation of phase space volume. Thus, if an energy exists in the above sense, statistical mechanics of the model can formally be constructed. If a locally defined quantity is conserved, however, it prevents the realization of statistical mechanics. The existence of such a quantity is examined for each class and a number of rules which have at least one energy but no local conservation laws are selected as hopeful candidates for the realization of thermodynamic behavior. In addition, the phase space structure of ERCAs is analyzed by enumerating cycles exactly in the phase space for systems of comparatively small sizes. As a result, it is revealed that a finite ERCA is not ergodic, that is, a large number of orbits coexist on an energy surface. It is argued that this fact does not necessarily mean the failure of thermodynamic behavior on the basis of an analogy with the ergodic nature of infinite systems.     

IPv6过渡机制讨论

本文在简要地介绍Ngtrans工作组提出的大多数过渡机制的基础上，尝试对它们进行区分、分类，并对每一种过渡机制的优缺点进行分析。另外．还对这些机制的布置以及一部分支持这些机制的产品平台进行讨论。     

On computation of the greatest common divisor of several polynomials over a finite field

We propose a probabilistic algorithm to reduce computing the greatest common divisor of m polynomials over a finite field (which requires computing m−1 pairwise greatest common divisors) to computing the greatest common divisor of two polynomials over the same field.