This paper presents an efficient Hybrid Learning Algorithm (HLA) for Radial Basis Function Neural Network (RBFNN). The HLA combines the gradient method and the linear least squared method for adjusting the RBF parameters and connection weights. The number of hidden neurons and their characteristics are determined using an unsupervised clustering procedure, and are used as input parameters to the learning algorithm. We demonstrate that the HLA, while providing faster convergence in training phase, is also less sensitive to training and testing patterns. The proposed HLA in conjunction with RBFNN is used as a classifier in a face recognition system to show the usefulness of the learning algorithm. The inputs to the RBFNN are the feature vectors obtained by combining shape information and Pseudo Zernike Moment (PZM). Simulation results on the Olivetti Research Laboratory (ORL) database and comparison with other algorithms indicate that the HLA yields excellent recognition rate with less hidden neurons in human face recognition.

This paper describes a stock trading system based on reinforcement learning, regarding the process of stock price changes as Markov decision process (MDP). The system adopts two popular reinforcement learning algorithms, temporal-difference (TD) and Q, for selecting stocks and optimizing trading parameters, respectively. Input features of the system are devised using technical analysis and value functions are approximated by feedforward neural networks. Multiple cooperative agents are used for Q-learning to efficiently integrate global trend prediction with local trading strategy. Agents communicate with others sharing training episodes and learned policies, while keeping the overall scheme of conventional Q-learning. Experimental results on the Korean stock market show that our trading system outperforms the market average and makes appreciable profits. Furthermore, we can find that our system is superior to a system trained by supervised learning in view of risk management.

It is known that all minimum cuts in an edge-weighted undirected graph with n vertices and m edges can be represented by a cactus with O(n) vertices and edges, a connected graph in which each edge is contained in an exactly one cycle. In this paper, we show that such a cactus representation can be computed in O(mn+n2log n) time and O(m) space. This improves the previously best complexity of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing a single minimum cut.

Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). It is known that any series-parallel simple graph G has an L-edge-coloring if either (i) |L(e)| max{4,d(v),d(w)} for each edge e=vw or (ii) the maximum degree of G is at most three and |L(e)| 3 for each edge e, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. In this paper we give a linear-time algorithm for finding such an L-edge-coloring of a series-parallel graph G.

An automated synthesis for analog computational circuits in transistor-level configuration is presented. A cell-based structure is introduced to place moderate constraints on the MOSFET circuit topology. Even though each cell has a simple structure that consists of one current path with four transistors, common analog building blocks can be implemented using combinations of the cells. A genetic algorithm is applied to search circuit topologies and transistor sizes that satisfy given specifications. Synthesis capabilities are demonstrated through examples of three types of computational circuits; absolute value, squaring, and cubing functions by using computer simulations and real hardware.

This paper defines the distributed arrangement selection problem in a line network in a distributed context and describes the design of a strictly-time-optimal algorithm which solves the problem with a limited local memory space. The problem is regarded as a combined distributed sorting and k-selection problem, namely a problem of sorting elements that are not larger than the kth minimum element in predetermined processes. The algorithm also provides a solution to a resource allocation problem in a line network in a strictly-optimal time.

We consider the routing for a multicast in a WDM all-optical network. We prove a min-max theorem on the number of wavelengths necessary for routing a multicast. Based on the min-max theorem, we propose an efficient on-line algorithm for routing a multicast.

Digital halftoning is a technique to convert a continuous-tone image into a binary image consisting of black and white dots. It is an important technique for printing machines and printers to output an image with few intensity levels or colors which looks similar to an input image. This paper surveys how algorithm engineering can contribute to digital halftoning or what combinatorial problems are related to digital halftoning. A common criterion on optimal digital halftoning leads to a negative result that obtaining an optimal halftoned image is NP-complete. So, there are two choices: approximation algorithm and polynomial-time algorithm with relaxed condition. Main algorithmic notions related are geometric discrepancy, matrix (or array) rounding problems, and network-flow algorithms.

We propose two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model. These algorithms are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the size of its shared memory is unbounded. Initially we design a provisional algorithm based on bounded tickets. It guarantees mutual exclusion in the case where a certain condition is satisfied. To remove the condition, we use an additional process that does not correspond to any user. The algorithm with the additional process is a lockout-free mutual exclusion algorithm on the asynchronous single-writer/multi-reader shared memory model. We then modify this algorithm to reduce the shared memory size with the cost of using another additional process. The maximum waiting time using each of the algorithms proposed in this paper is bounded by (n-1)c+O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n+1)(1+log (4n)) bits and n(1+log (4n-4))+2 bits, respectively.

In this paper, we consider the problem of multicasting a message in k-ary n-cubes under the store-and-forward model. The objective of the problem is to minimize the size of the resultant multicast tree by keeping the distance to each destination over the tree the same as the distance in the original graph. In the following, we first propose an algorithm that grows a multicast tree in a greedy manner, in the sense that for each intermediate vertex of the tree, the outgoing edges of the vertex are selected in a non-increasing order of the number of destinations that can use the edge in a shortest path to the destination. We then evaluate the goodness of the algorithm in terms of the worst case ratio of the size of the generated tree to the size of an optimal tree. It is proved that for any k 5 and n 6, the performnance ratio of the greedy algorithm is c kn - o(n) for some constant 1/12 c 1/2.

This paper presents a new sliding window algorithm that is well-suited to an elliptic curve defined over an extension field for which the Frobenius map can be computed quickly, e.g., optimal extension field. The algorithm reduces elliptic curve group operations by approximately 15% for scalar multiplications for a practically used curve in compared to Lim-Hwang's results presented at PKC2000, which was the fastest previously reported. The algorithm was implemented on computers. Scalar multiplication can be accomplished in 573 µs, 595 µs, and 254 µs on Pentium II (450 MHz), 21164A (500 MHz), and 21264 (500 MHz) computers, respectively.

A digit-recurrence algorithm for computing reciprocal square-root which appears frequently in multimedia and graphics applications is proposed. The reciprocal square-root is computed by iteration of carry-propagation-free additions, shifts, and multiplications by one digit. Different specific versions of the algorithm are possible, depending on the radix, the redundancy factor of the digit set, and etc. Details of a radix-2 version and a radix-4 version and designs of a floating-point reciprocal square-root circuit based on them are shown.

This letter presents parallel algorithms for matrix multiplication and the fast Fourier transform (FFT) that are significant problems arising in engineering and scientific applications. The proposed algorithms are designed on a 3-dimensional processor array with separable buses (PASb). We show that a PASb consisting of N N h processors can compute matrix multiplication of size N N and the FFT of size N in O(N/h+log N) time, respectively. In order to examine ease of hardware implementation, we also evaluate the VLSI complexity of the algorithms. A result obtained achieves an optimal bound on area-time complexity when h=O(N/log N).

This paper describes a rhythm pattern accuracy diagnosis system based on the rhythm pattern matching algorithm and a diagnosis feedback method by employing the SVM technique. A beat rhythm pattern is recorded by a PC and analyzed with an algorithm including cluster-analysis-based pattern matching. Rhythm performance is represented by a performance feature vector, which features note length deviation, note length instability, and tempo instability. The performance feature vector is effective for objectively evaluating the accuracy of rhythm patterns objectively. In addition, this system has the music experts' knowledge base, which is calculated from the performance feature vectors associated with the experts' subjective evaluation by listening to the performance. The system generates both an objective measuring report, and experts' comments for learners. Reproductivity of experts' comments is statistically indicated to be excellent for eight rhythm patterns, two tempo levels, and eight users. Reliability of experts' comments are also described considering the threshold of the decision function of SVM. Subjective evaluation of the system is carried out by fifteen users by a questionnaire using the SD method. As a result of factor analysis for the sixteen questions, four factors named "Audio-visual representation," "User-friendliness," "Reliability," and "Window representation," are extracted. Users' four factor scores indicate that the system is reliable and easy to use.

In this paper, we propose a novel 2D plenoptic function called "acentric panorama view (APV)." This novel 2D plenoptic function samples the panorama scenes without oversampling or undersampling. A single APV can be accelerated by view culling and list-priority rendering algorithm. Multiple APVs with special fields of view, 45, 60, 90, and 120, can be integrated into a larger configuration called augmented APVs, which can augment the walking area in a planar walkthrough environment to form a 4D plenoptic function. In augmented APVs, the acceleration schemes of a single APV can still be applied successfully.

The modern network service of finding the optimal path subject to multiple constraints on performance metrics such as delay, jitter, loss probability, etc. gives rise to the multi-constrained optimal-path (MCOP) QoS routing problem, which is NP-complete. In this paper, this problem is solved through both exact and heuristic algorithms. We propose an exact algorithm E_MCOP, which first constructs an aggregate weight and then uses a K-shortest-path algorithm to find the optimal solution. By means of E_MCOP, the performance of the heuristic algorithm H_MCOP proposed by Korkmaz et al. in a recent work is evaluated. H_MCOP only runs Dijkstra's algorithm (with slight modifications) twice, but it can find feasible paths with a success ratio very close to that of the exact algorithm. However, we notice that in certain cases its feasible solution has an unsatisfactorily high average cost deviation from the corresponding optimal solution. For this reason, we propose some modified algorithms based on H_MCOP that can significantly improve the performance by running Dijkstra's algorithm a few more times. The performance of the exact algorithm and heuristics is investigated through computer simulations on networks of various sizes.

In this paper, we propose a medium access control (MAC) protocol for multimedia code division multiple access (CDMA) communications. In the proposed protocol, a base station (BS) estimates the instantaneous number of simultaneously transmitted packets in the future slots with exploiting a stochastic property of traffic. In order to carry out this estimation, we employ an adaptive algorithm. We evaluate the performance of the proposed protocol by comparing that with two different cases. One is no estimation case and the other is perfect estimation case. From these results, we clarify the advantage of the proposed MAC protocol.

This paper describes special-purpose hardware for large-scale logic simulation, called SP2, which executes an event driven algorithm and can simulate up to sixteen million gates. SP2 was developed, in 1992, for system verification of large-scale computer designs as a successor to SP1, which was developed in 1987. SP2 provides enhanced performance, throughput, and delay accuracy over SP1. Since 1992, SP2 has been widely used for system-level simulation of mainframes, super computers, UNIX servers and microprocessors. It is used as a powerful simulator, in all stages of design verification, or in early stages, before regression testing, by using emulators.

The problem of the super-resolution time delay estimation of the real stationary signals is addressed in this paper. The time delay estimation is first converted into a frequency estimation problem. Then a MUSIC-type algorithm to estimate the subsequent frequency from the single-experiment data is proposed, which not only avoids the mathematical model mismatching but also utilizes the advantages of the subspace-based methods. The mean square errors (MSEs) of the time delay estimate of the MUSIC-type method for varying signal-to-noise (SNR) and separation of two received signal components are shown to illustrate that they approximately coincide with the corresponding Cramer-Rao bound (CRB). Finally, the comparison between the MUSIC-type method and the other conventional methods is presented to show the advantages of the proposed method in this paper.

We suggest a new probe message structure and an efficient probe-based deadlock detection and recovery algorithm that can be used in distributed database systems. We determine the characteristics of the probe messages and suggest an algorithm that can reduce the communication cost required for deadlock detection and recovery.