A simple approximation algorithm for the weighted matching problem

We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259-269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time.     

Response level crossing rate of a linear system excited by a partially specified Gaussian load process

The problem of determining the maximum mean response level crossing rate of a linear system driven by a partially specified Gaussian load process has been considered. The partial specification of the load is given only in terms of its total average energy. The critical input power spectral (PSD) function, which maximizes the mean response level crossing rate, is obtained. The critical input PSD turns out to be highly narrow-banded which fails to capture the erratic nature of the excitation. Consequently, the trade-off curve between the maximum mean response level crossing rate and the maximum disorder in the input process, quantified in terms of its entropy rate, has been generated. The method of Pareto optimization is used to tackle the conflicting objectives of the simultaneous maximization of the mean response level crossing rate and the input entropy rate. The non-linear multi-objective optimization has been carried out using a recently developed multi-criteria genetic algorithm scheme. Illustrative example of determining the critical input of an axially vibrating rod, excited by a partially specified stationary Gaussian load process, has been considered.     

A Search for Hidden Relationships: Data Mining with Genetic Algorithms

This paper presents an algorithm that permits the search for dependencies among sets of data (univariate or multivariate time-series, or cross-sectional observations). The procedure is modeled after genetic theories and Darwinian concepts, such as natural selection and survival of the fittest. It permits the discovery of equations of the data-generating process in symbolic form. The genetic algorithm that is described here uses parts of equations as building blocks to breed ever better formulas. Apart from furnishing a deeper understanding of the dynamics of a process, the method also permits global predictions and forecasts. The algorithm is successfully tested with artificial and with economic time-series and also with cross-sectional data on the performance and salaries of NBA players during the 94–95 season.     

Adaptive solutions to the mutual exclusion problem

Summary Algorithms for mutual exclusion that adapt to the current degree of contention are developed. Afilter and a leader election algorithm form the basic building blocks. The algorithms achieve system response times that are independent of the total number of processes and governed instead by the current degree of contention. The final algorithm achieves a constant amortized system response time. Manhoi Choy was born in 1967 in Hong Kong. He received his B.Sc. in Electrical and Electronic Engineerings from the University of Hong Kong in 1989, and his M.Sc. in Computer Science from the University of California at Santa Barbara in 1991. Currently, he is working on his Ph.D. in Computer Science at the University of California at Santa Barbara. His research interests are in the areas of parallel and distributed systems, and distributed algorithms. Ambuj K. Singh is an Assistant Professor in the Department of Computer Science at the University of California, Santa Barbara. He received a Ph.D. in Computer Science from the University of Texas at Austin in 1989, an M.S. in Computer Science from Iowa State University in 1984, and a B.Tech. from the Indian Institute of Technology at Kharagpur in 1982. His research interests are in the areas of adaptive resource allocation, concurrent program development, and distributed shared memory.A preliminary version of the paper appeared in the 12th Annual ACM Symposium on Principles of Distributed ComputingWork supported in part by NSF grants CCR-9008628 and CCR-9223094     

A pattern recognition-based approach for phylogenetic network construction with constrained recombination

The tree representation of evolutionary relationship oversimplifies the view of the process of evolution as it cannot take into account the events such as horizontal gene transfer, hybridization, homoplasy and genetic recombination. Several algorithms exist for constructing phylogenetic networks which result from events such as horizontal gene transfer, hybridization and homoplasy. Very little work has been published on the algorithmic detail of phylogenetic networks with constrained recombination. The problem of minimizing the number of recombinations in a phylogenetic network, constructed using binary DNA sequences, is NP-hard. In this paper, we propose a pattern recognition-based O(n²) time approach for constructing the phylogenetic network, where n is the number of nodes or sequences in the input data. The network is constructed with the restriction that no two cycles in the network share a common node.     

从数据结构角度设计导游系统

从数据结构角度为旅游胜地设计导游系统。向游人提供景点的信息查询服务,根据指定的景点提供相关的景点信息。任意给定起点和终点,查询两点之间的最短路径。     

激光切割工艺参数优化数据库系统

用Visual Basic 6.0和用SQL server 7.0设计了激光切割工艺参数数据查询系统.能实现对常用材料的激光切割工艺参数进行查询.同时,提供了方便的数据库维护方法,提出用户基于Web技术的数据库更新方法.     

A genetic‐based neuro‐fuzzy controller for blind equalization of time‐varying channels

This paper presents a neuro‐fuzzy network (NFN) where all its parameters can be tuned simultaneously using genetic algorithms (GAs). The approach combines the merits of fuzzy logic theory, neural networks and GAs. The proposed NFN does not require a priori knowledge about the system and eliminates the need for complicated design steps such as manual tuning of input–output membership functions, and selection of fuzzy rule base. Although, only conventional GAs have been used, convergence results are very encouraging. A well‐known numerical example derived from literature is used to evaluate and compare the performance of the network with other equalizing approaches. Simulation results show that the proposed neuro‐fuzzy controller, all parameters of which have been tuned simultaneously using GAs, offers advantages over existing equalizers and has improved performance. From the perspective of application and implementation, this paper is very interesting as it provides a new method for performing blind equalization. The main contribution of this paper is the use of learning algorithms to train a feed‐forward neural network for M‐ary QAM and PSK signals. This paper also provides a platform for researchers of the area for further development. Copyright © 2008 John Wiley & Sons, Ltd.     

On collaborative content distribution using multi-message gossip

We study epidemic schemes in the context of collaborative data delivery. In this context, multiple chunks of data reside at different nodes, and the challenge is to simultaneously deliver all chunks to all nodes.