A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks

In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub‐graph. However, finding the minimum connected dominating set (MCDS) is a well‐known NP‐hard problem in graph theory. Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity. In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one‐hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright © 2005 John Wiley & Sons, Ltd.     

Extending boosting for large scale spoken language understanding

We propose three methods for extending the Boosting family of classifiers motivated by the real-life problems we have encountered. First, we propose a semisupervised learning method for exploiting the unlabeled data in Boosting. We then present a novel classification model adaptation method. The goal of adaptation is optimizing an existing model for a new target application, which is similar to the previous one but may have different classes or class distributions. Finally, we present an efficient and effective cost-sensitive classification method that extends Boosting to allow for weighted classes. We evaluated these methods for call classification in the AT&;T VoiceTone^® spoken language understanding system. Our results indicate that it is possible to obtain the same classification performance by using 30% less labeled data when the unlabeled data is utilized through semisupervised learning. Using model adaptation we can achieve the same classification accuracy using less than half of the labeled data from the new application. Finally, we present significant improvements in the “important” (i.e., higher weighted) classes without a significant loss in overall performance using the proposed cost-sensitive classification method.     

Age of acquisition: Its neural and computational mechanisms.

The acquisition of new skills over a life span is a remarkable human ability. This ability, however, is constrained by age of acquisition (AoA); that is, the age at which learning occurs significantly affects the outcome. This is most clearly reflected in domains such as language, music, and athletics. This article provides a perspective on the neural and computational mechanisms underlying AoA in language acquisition. The authors show how AoA modulates both monolingual lexical processing and bilingual language acquisition. They consider the conditions under which syntactic processing and semantic processing may be differentially sensitive to AoA effects in second-language acquisition. The authors conclude that AoA effects are pervasive and that the neural and computational mechanisms underlying learning and sensorimotor integration provide a general account of these effects. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

计算机远程控制系统的设计与实现

介绍了一个计算机远程控制系统的设计与实现，该系统采用客户机／服务器模式，实现远程屏幕的实时传输，采用LZW压缩算法对图像进行压缩传输，在接受方进行解码并且实现了远程文件创建和删除、显示被控制端的主机信息、发送实时消息等功能。采用鼠标，键盘的模拟方式对计算机进行实时控制。     

David W. Johnson: Award for Distinguished Contributions of Applications of Psychology to Education and Training.

Provides the biography of David W. Johnson and announces that he has won the Award for Distinguished Contributions of Applications of Psychology to Education and Training for programmatic research, comprehensive research reviews, and revision of theory over four decades of persistence that have provided the knowledge foundation for cooperative learning, constructive controversy, conflict resolution, and peer mediation training. A selected bibliography is also provided. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

天然气管网输配气量优化研究

天然气管网系统管理部门为了明确天然气管网的输气能力和提高天然气管网的利用率，需要对天然气管网系统的输配气量进行优化。为此，以天然气管网系统的最大流量为目标函数，同时考虑了管道强度、节点压力和流量限制等约束条件，建立了天然气管网输配气量优化的数学模型。在研究遗传算法和模拟退火算法的基础上，提出了一种由二者结合构成的具有全域搜索、快速收敛和鲁棒性强等特点的混合遗传算法。结合实例，采用这一新算法求解了天然气管网输配气量优化的数学模型。实例优化结果表明，所建立的数学模型和采用的混合遗传算法是可行和有效的，能够对天然气管网系统输配气量的调度运行起到指导作用。     

Note on ‘Construction of Double Sampling s‐Control Charts for Agile Manufacturing’

He and Grigoryan (Quality and Reliability Engineering International 2002; 18 :343–355) formulated the design of a double‐sampling (DS) s control chart as an optimization problem and solved it with a genetic algorithm. They concluded that the DS s control charts can be a more economically preferable alternative in detecting small shifts than traditional s control charts. We explain that, since they only considered the average sample size when the process is in control, their conclusion is questionable. Copyright © 2006 John Wiley & Sons, Ltd.     

A parallel and scalable algorithm for ADI method with pre-propagation and message vectorization

It is hard to implement the ADI method in an efficient way on distributed-memory parallel computers. We propose “P-scheme” which parallelizes a tridiagonal linear system of equations for the ADI method, but its effectiveness is limited to the cases where the problem size is large enough mainly because of the communication cost of the propagation phase of the scheme.

In order to overcome this difficulty, we propose an improved version of the P-scheme with “message vectorization” which aggregates several communication messages into one and alleviates the communication cost. Also we evaluate the effectiveness of message vectorization for the ADI method and show that the improved version of the P-scheme works well even for smaller problems and linear and super-linear speedups can be achieved for 8194 × 8194 and 16,386 × 16,386 problems, respectively.     

Estimation for the number of components in a mixture model using stepwise split-and-merge EM algorithm

The main difficulty with EM algorithm for mixture model concerns the number of components, say g. This is the question of model selection, and the EM algorithm itself could not estimate g. On the contrary, the algorithm requires g to be specified before the remaining parameters can be estimated. To solve this problem, a new algorithm, which is called stepwise split-and-merge EM (SSMEM) algorithm, is proposed. The SSMEM algorithm alternately splits and merges components, estimating g and other parameters of components simultaneously. Also, two novel criteria are introduced to efficiently select the components for split or merge. Experimental results on simulated and real data demonstrate the effectivity of the proposed algorithm.     

Employing optimized combinations of one-class classifiers for automated currency validation

Automated currency validation requires a decision to be made regarding the authenticity of a banknote presented to the validation system. This decision often has to be made with little or no information regarding the characteristics of possible counterfeits as is the case for issues of new currency. A method for automated currency validation is presented which segments the whole banknote into different regions, builds individual classifiers on each region and then combines a small subset of the region specific classifiers to provide an overall decision. The segmentation and combination of region specific classifiers to provide optimized false positive and false negative rates is achieved by employing a genetic algorithm. Experiments based on high value notes of Sterling currency were carried out to assess the effectiveness of the proposed solution.