Spiral hashing is a well known dynamic hashing algorithm. Traditional analysis of this search algorithm has been proposed under the assumption that all keys are uniformly accessed. In this paper, we present a discrete analysis of the average search cost in consideration of the frequency of access on each key for this spiral hashing algorithm. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. The evaluate formulae derived from the proposed analysis can exactly evaluate the average and variance of the search cost in conformity with any probability distribution of the frequency of access.

The paper presents a topology-oriented robust algorithm for the incremental construction of line arrangements. In order to achieve a robust implementation, the topological and geometrical computations are strictly separated. The topological part is proved to be reliable without any assumption on the accuracy of the geometrical part. A self-correcting property is introduced to minimize the effect of numerical errors. Computational experiments show how the self-correcting property works, and we also discuss some applications of the algorithm.

The detection of timing constraint violation is crucial in reactive systems. A method of detecting deadline violation based on Floyd-Warshall shortest path algorithm has been proposed by Chodrow et al. We extend this method to detect the violation of minimum delay time in reactive systems where the repetition of event sequences frequently occurs.

The redundancy allocation problem for a series-parallel system is a well known as one of NP-hard combinatorial problems and it generally belongs to the class of nonlinear integer programming (nIP) problem. Many researchers have developed the various methods which can be roughly categorized into exact solution methods, approximate methods, and heuristic methods. Though each method has both advantages and disadvantage, the heuristic methods have been received much attention since other methods involve more computation effort and usually require larger computer memory. Genetic algorithm (GA) as one of heuristic optimization techniques is a robust evolutionary optimization search technique with very few restrictions concerning with the various design problems. However, GAs cannot guarantee the optimality and sometimes can suffer from the premature convergence situation of its solution, because it has some unknown parameters and it neither uses a priori knowledge nor exploits the local search information. To improve these problems in GA, this paper proposes an effective hybrid genetic algorithm based on, 1) fuzzy logic controller (FLC) to automatically regulate GA parameters and 2) incorporation of the iterative hill climbing method to perform local exploitation around the near optimum solution for solving redundancy allocation problem. The effectiveness of this proposed method is demonstrated by comparison results with other conventional methods on two different types of redundancy allocation problems.

In computer-aided drafting and design, interactive graphics is used to design components, systems, layouts, and structures. There are several approaches for using automated graphical layout tools currently. Our approach employs a genetic algorithm to implement a tool for automated 3D graphical layout design and presentation. The effective use of a genetic algorithm in automated graphical layout design relies on defining a fitness function that reflects user preferences. In this paper, we describe a method to define fitness functions and chromosome structures of selected objects. A learning mechanism is employed to adjust the fitness values of the objects in the selected layout chosen by the user. In our approach, the fitness functions can be changed adaptively reflecting user preferences. Experimental results revealed good performance of the adaptive fitness functions in our proposed mechanism.

Recently, feature maps have been applied to various problem domains. The success of some of these applications critically depends on whether feature maps are topologically ordered. Several different approaches have been proposed to improve the conventional self-organizing feature map (SOM) algorithm. However, these approaches do not guarantee that a topologically-ordered feature map can be formed at the end of a simulation. Therefore, the trial-and-error procedure still dominates the procedure of forming feature maps. In this paper, we propose a healing mechanism to repair feature maps that are not well topologically ordered. The healed map is then further fine-tuned by the conventional SOM algorithm with a small learning rate and a small-sized neighborhood set so as to improve the accuracy of the map. Two data sets were tested to illustrate the performance of the proposed method.

The group organization used for group learning in a knowledge intensive domain like software development affects educational achievement. This paper proposes a group organization system for software engineering education done through group learning. The organizational problem itself is defined and why a Genetic Algorithm (GA) is an appropriate means of solving this problem is explained. This system is a Web application developed with open source software and runs on an open source software platform. Based on the group organization data collected from actual classes, we generated various group organizations by using different strategy parameter values. We then gave a questionnaire to actual students asking them which solution produced the fairest group organization. The replies received revealed that the candidate solution that set greater weight on leadership capability and system analysis capability was the fairest.

In this paper, we study system-level diagnosis under the comparison approach proposed by Maeng and Malek. Sengupta and Dahbura designed an O(n5) time diagnosis algorithm for identifying all faulty nodes in general graphs (n is the number of nodes in a system). We consider diagnosis on a butterfly network BF(k,r) and propose O(k2 n) time diagnosis algorithms for locating all faulty nodes in BF(k,r).

The Task-Coalition Assignment Problem (TCAP) is a formalization of the distributed computation problem. In TCAP, a set of agents and a set of tasks are given. A subset of the agents processes a task to produce benefit. The goal of TCAP is to find the combination of the tasks and the subsets of the agents that maximizes the sum of the benefit. In this paper, we define 1-TCAP, which is a practical subclass of TCAP. In 1-TCAP, tasks and agents are characterized by scalar values. We propose a polynomial-time approximation algorithm for 1-TCAP, and show that this algorithm achieves an approximation ratio 9/4. Here, an algorithm achieves an approximation ratio α for a maximization problem if, for every instance, it produces a solution of value at least OPT/α, where OPT is the value of the optimal solution.

This paper describes the outline of the active noise control system and the adaptive signal processing used in the practical systems. Focus is on the adaptive signal processing and algorithms which are widely used in many applications. Some variations in the algorithms for improving the control effect and for reducing the amount of calculation are also shown. Additionally, the limitations and some design guide are shown with the results of the numerical simulations.

The major concern at a branch point in asynchronous transfer mode (ATM) networks for point-to-multipoint available bit rate (ABR) services is how to consolidate backward resource management (BRM) cells from each branch for a multicast connection. In this paper, we propose an efficient feedback consolidation algorithm based on an adaptive dynamic threshold (ADT) to eliminate consolidation noise and to reduce consolidation delay. The main idea of the ADT algorithm is that each branch point estimates the ABR traffic condition of the network through virtual queue estimation. Simulation results show that the proposed ADT algorithm can achieve a faster response in congestion status and a higher link utilization compared with the previous works.

An advanced center biased search algorithm for block motion estimation is proposed in this letter. It adopts an innovative center biased search strategy to get correct motion vector. The computational complexity is reduced by strict application of the unimodal error surface assumption and half stop technique. Experimental results show that proposed algorithm has improved performance as compared to the conventional block matching algorithms.

A Wireless Sensor Network (WSN, for short) is a distributed system consisting of n sensor nodes and a base station. In this paper, we propose an energy-efficient protocol to initialize the sensor nodes in a WSN, that is, to assign a unique ID to each sensor node. We show that if an upper bound u on the number n of sensor nodes is known beforehand, for any f 1 and any small µ (0<µ<1), a WSN without collision detection capability can be initialized in O((log (1/µ) + log f)u1+µ) time slots, with probability exceeding 1-(1/f), with no sensor node being awake for more than O(log (1/µ)+ log f) time slots.

A novel rough neural network (RNN) structure and its application are proposed in this paper. We principally introduce its architecture and training algorithms: the genetic training algorithm (GA) and the tabu search training algorithm (TSA). We first compare RNN with the conventional NN trained by the BP algorithm in two-dimensional data classification. Then we compare RNN with NN by the same training algorithm (TSA) in functional approximation. Experiment results show that the proposed RNN is more effective than NN, not only in computation time but also in performance.

It has been shown that virtual output queuing (VOQ) and a sophisticated scheduling algorithm enable an input-queued switch to achieve 100% throughput for independent arrival process. Several of the scheduling algorithms that have been proposed can be classified as either iterative scheduling algorithms or symmetric crossbar arbitration algorithms. i-OCF (oldest-cell-first) and TSA (two step arbiter) are well-known examples of iterative scheduling algorithms and symmetric crossbar arbitration algorithms, respectively. However, there are drawbacks in using these algorithms. i-OCF takes long time to find completely a conflict-free match between input ports and output ports because it requires multiple iterations. If i-OCF cannot find a conflict-free match completely, the switch throughput falls. TSA has the possibility that it finds a conflict-free match faster than i-OCF because it does not need any iterations. However, TSA suffers from the starvation problem. In this paper, we propose a new scheduling algorithm. It uses two schedulers, which we call scheduler 1 and scheduler 2, in parallel. After cells were transmitted, the information that input port i granted the offer from output port j in scheduler 2 is mapped to scheduler 1 if and only if input port i has at least one cell destined for output port j. If the information is moved, input port i and output port j are matched in scheduler 1 at the beginning of the next time slot. Our proposed algorithm uses one scheduler based on TSA and the other scheduler based on i-OCF. Numerical results show that the proposed scheduling algorithm does not require multiple iterations to find a conflict-free match completely and suffer from the starvation problem for both uniform and bursty traffic.

In this study, a hybrid genetic algorithm/neural network with fuzzy logic controller (NN-flcGA) is proposed to find the global optimum of reliability assignment/redundant allocation problems which should be simultaneously determined two different types of decision variables. Several researchers have obtained acceptable and satisfactory results using genetic algorithms for optimal reliability assignment/redundant allocation problems during the past decade. For large-size problems, however, genetic algorithms have to enumerate numerous feasible solutions due to the broad continuous search space. Recently, a hybridized GA combined with a neural network technique (NN-hGA) has been proposed to overcome this kind of difficulty. Unfortunately, it requires a high computational cost though NN-hGA leads to a robuster and steadier global optimum irrespective of the various initial conditions of the problems. The efficacy and efficiency of the NN-flcGA is demonstrated by comparing its results with those of other traditional methods in numerical experiments. The essential features of NN-flcGA namely, 1) its combination with a neural network (NN) technique to devise initial values for the GA, 2) its application of the concept of a fuzzy logic controller when tuning strategy GA parameters dynamically, and 3) its incorporation of the revised simplex search method, make it possible not only to improve the quality of solutions but also to reduce computational cost.

The mobile computing system is a set of functions on a distributed environment organized to support mobile hosts. In this environment, mobile hosts should be able to move without any constraints and should remain connected to the network even while moving. Also, they should be able to get necessary information regardless of their current location and time. Distributed mutual exclusion methods for supporting distributed algorithms have hitherto been designed for networks only with static hosts. However, with the emergence of mobile computing environments, a new distributed mutual exclusion method needs to be developed for integrating mobile hosts with underlying distributed systems. In the sense, many issues that should be considered stem from three essential properties of mobile computing system such as wireless communication, portability, and mobility. Thus far, distributed mutual exclusion methods for mobile computing environments were designed based on a token ring structure, which has the drawback of requiring high costs in order to locate mobile hosts. In this paper, we propose not only a distributed mutual exclusion method that can reduce such costs by structuring the entire system as a tree-based logical structure but also recovery schemes that can be applied when a node failure occurs. Finally, we evaluate the operation costs for the mutual exclusion scheme and the recovery scheme.

Several implementation methods for a MAP decoder are proposed in this paper. Using a novel pipeline structured time-shared process, the authors are able to efficiently overcome the restrictions imposed by the recursion process on state metrics, and the complexity of the MAP decoder can be reduced to a level on the order of a SOVA (Soft Output Viterbi Algorithm) decoder. In addition, the authors propose an efficient controller structure that can be used for variable frame-size systems such as cdma-2000. The MAP decoder using a block-wise algorithm designed here was implemented in only one 20,000 gate circuit. It was validated by VHDL, which was compared with the results of the initial simulation (C programs). The decoder demonstrated a 300 kbps decoding processing ability with 8 iterations on a FPGA circuit, with a deviation only about 0.1-0.2 dB greater than that for an ideal MAP decoder, even when all hardware environments are considered.

Y. S. Han et al. have proposed an efficient maximum likelihood decoding (MLD) algorithm using A* algorithm which is the graph search method. In this paper, we propose a new MLD algorithm for linear block codes. The MLD algorithm proposed in this paper improves that given by Han et al. utilizing codewords of dual codes. This scheme reduces the number of generated codewords in the MLD algorithm. We show that the complexity of the proposed decoding algorithm is reduced compared to that given by Han et al. without increasing the probability of decoding error.

We consider to design approximation algorithms for the survivable network design problem in hypergraphs (SNDPHG) based on algorithms developed for the survivable network design problem in graphs (SNDP) or the element connectivity problem in graphs (ECP). Given an instance of the SNDPHG, by replacing each hyperedge e={v1,,vk} with a new vertex we and k edges {we, v1},, {we, vk}, we define an SNDP or ECP in the resulting graph. We show that by approximately solving the SNDP or ECP defined in this way, several approximation algorithms for the SNDPHG can be obtained. One of our results is a dmax+-approximation algorithm for the SNDPHG with dmax 3, where dmax (resp. dmax+) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a dmax+(rmax)-approximation algorithm for the SNDPHG, where (i)=j=1i(1/j) is the harmonic function and rmax is the maximum connectivity requirement.