This paper investigates migration effects of parallel genetic algorithms (GAs) on the line topology of heterogeneous computing resources. Evolution process of parallel GAs is evaluated experimentally on two types of arrangements of heterogeneous computing resources: the ascending and descending order arrangements. Migration effects are evaluated from the viewpoints of scalability, chromosome diversity, migration frequency and solution quality. The results reveal that the performance of parallel GAs strongly depends on the design of the chromosome migration in which we need to consider the arrangement of heterogeneous computing resources, the migration frequency and so on. The results contribute to provide referential scheme of implementation of parallel GAs on heterogeneous computing resources.

In IEEE 802.11 networks, the access point (AP) selection based on the strongest signal strength often results in the extremely unfair bandwidth allocation among mobile users (MUs). In this paper, we propose a distributed AP selection algorithm to achieve a fair bandwidth allocation for MUs. The proposed algorithm gradually balances the AP loads based on max-min fairness for the available multiple bit rate choices in a distributed manner. We analyze the stability and overhead of the proposed algorithm, and show the improvement of the fairness via computer simulation.

A design method is proposed for a low-profile dual-shaped reflector antenna for the mobile satellite communications. The antenna is required to be low-profile because of mount restrictions. However, reduction of its height generally causes degradation of antenna performance. Firstly, an initial low-profile reflector antenna with an elliptical aperture is designed by using Geometrical Optics (GO) shaping. Then a Physical Optics (PO) shaping technique is applied to optimize the gain and sidelobes including mitigation of undesired scattering. The developed design method provides highly accurate design procedure for electrically small reflector antennas. Fabrication and measurement of a prototype antenna support the theory.

A branch-and-bound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems. Even if it is used, computation time is likely to increase exponentially. So we consider its parallelization to reduce it. It has been reported that the computation time of a parallel BB heavily depends upon node-variable selection strategies. And, in case of a parallel BB, it is also necessary to prevent increase in communication time. So, it is important to pay attention to how many and what kind of nodes are to be transferred (called sending-node selection strategy). In this paper, for the graph coloring problem, we propose some sending-node selection strategies for a parallel BB algorithm by adopting MPI for parallelization and experimentally evaluate how these strategies affect computation time of a parallel BB on a PC cluster network.

We present a TCP flow level performance evaluation on error rate aware scheduling algorithms in Evolved UTRA and UTRAN networks. With the introduction of the error rate, which is the probability of transmission failure under a given wireless condition and the instantaneous transmission rate, the transmission efficiency can be improved without sacrificing the balance between system performance and user fairness. The performance comparison with and without error rate awareness is carried out dependant on various TCP traffic models, user channel conditions, schedulers with different fairness constraints, and automatic repeat request (ARQ) types. The results indicate that error rate awareness can make the resource allocation more reasonable and effectively improve the system and individual performance, especially for poor channel condition users.

In this paper, a block-constrained trellis coded quantization (BC-TCQ) algorithm is combined with an algebraic codebook to produce an algebraic trellis code (ATC) to be used in ACELP coding. In ATC, the set of allowed algebraic codebook pulse positions is expanded, and the expanded set is partitioned into subsets of pulse positions; the trellis branches are labeled with these subsets. The list Viterbi algorithm (LVA) is used to select the excitation codevector. The combination of an ATC codebook and LVA trellis search algorithm is denoted as an ATC-LVA block code. The ATC-LVA block code is used as the fixed codebook of the AMR-WB 8.85 kbps mode, reducing complexity compared to the conventional algebraic codebook.

This paper presents a low complexity algorithmic framework for finding a broadcasting schedule in a low-altitude satellite system, i.e., the satellite broadcast scheduling (SBS) problem, based on the recent modeling and computational methodology of factor graphs. Inspired by the huge success of the low density parity check (LDPC) codes in the field of error control coding, in this paper, we transform the SBS problem into an LDPC-like problem through a factor graph instead of using the conventional neural network approaches to solve the SBS problem. Based on a factor graph framework, the soft-information, describing the probability that each satellite will broadcast information to a terminal at a specific time slot, is exchanged among the local processing in the proposed framework via the sum-product algorithm to iteratively optimize the satellite broadcasting schedule. Numerical results show that the proposed approach not only can obtain optimal solution but also enjoys the low complexity suitable for integral-circuit implementation.

This paper proposes a likelihood estimation method for reduced-complexity maximum-likelihood (ML) detectors in a multiple-input multiple-output (MIMO) spatial-multiplexing (SM) system. Reduced-complexity ML detectors, e.g., Sphere Decoder (SD) and QR decomposition (QRD)-M algorithm, are very promising as MIMO detectors because they can estimate the ML or a quasi-ML symbol with very low computational complexity. However, they may lose likelihood information about signal vectors having the opposite bit to the hard decision and bit error rate performance of the reduced-complexity ML detectors are inferior to that of the ML detector when soft-decision decoding is employed. This paper proposes a simple estimation method of the lost likelihood information suitable for the reduced-complexity ML detectors. The proposed likelihood estimation method is applicable to any reduced-complexity ML detectors and produces accurate soft-decision bits. Computer simulation confirms that the proposed method provides excellent decoding performance, keeping the advantage of low computational cost of the reduced-complexity ML detectors.

We propose a fast decoding algorithm for the p-ary first-order Reed-Muller code guaranteeing correction of up to errors and having complexity proportional to nlog n, where n = pm is the code length and p is an odd prime. This algorithm is an extension in the complex domain of the fast Hadamard transform decoding algorithm applicable to the binary case.

A new adaptive filter algorithm based on the linear prediction property of sinusoidal signals is proposed for unbiased estimation of the frequency of a real tone in white noise. Similar to the least mean square algorithm, the estimator is computationally simple and it provides unbiased as well as direct frequency measurements. Learning behavior and variance of the estimated frequency are derived and confirmed by computer simulations.

Learning for boltzmann machines deals with each state individually. If given data is categorized, the probabilities have to be distributed to each state, not to each catetory. We propose boltzmann machines identifying the states in the same categories. Boltzmann machines with hidden units are the special cases. Boltzmann learning and em algorithm are effective learning methods for boltzmann machines. We solve boltzmann learning and em algorithm for the proposed models.

This letter presents a new inter-cluster proximity index for fuzzy partitions obtained from the fuzzy c-means algorithm. It is defined as the average proximity of all possible pairs of clusters. The proximity of each pair of clusters is determined by the overlap and the separation of the two clusters. The former is quantified by using concepts of Fuzzy Rough sets theory and the latter by computing the distance between cluster centroids. Experimental results indicate the efficiency of the proposed index.

The research on displacement vector detection has gained increasing attention in recent years. However, no relationship between displacement vectors and the outlines of objects in motion has been established. We describe a new method of detecting displacement vectors through edge segment detection by emphasizing the correlation between displacement vectors and their outlines. Specifically, after detecting an edge segment, the direction of motion of the edge segment can be inferred through the variation in the values of the Laplacian-Gaussian filter at the position near the edge segment before and after the motion. Then, by observing the degrees of displacement before and after the motion, the displacement vector can be calculated. The accuracy compared to other methods of displacement vector detection demonstrates the feasibility of this method.

Permutation ambiguity of the classical Independent Component Analysis (ICA) may cause problems in feature extraction for pattern classification. Especially when only a small subset of components is derived from data, these components may not be most distinctive for classification, because ICA is an unsupervised method. We include a selective prior for de-mixing coefficients into the classical ICA to alleviate the problem. Since the prior is constructed upon the classification information from the training data, we refer to the proposed ICA model with a selective prior as a supervised ICA (sICA). We formulated the learning rule for sICA by taking a Maximum a Posteriori (MAP) scheme and further derived a fixed point algorithm for learning the de-mixing matrix. We investigate the performance of sICA in facial expression recognition from the aspects of both correct rate of recognition and robustness even with few independent components.

This work describes a 12 b 200 kS/s 0.52 mA 0.47 mm2 ADC for sensor applications such as motor control, 3-phase power control, and CMOS image sensors simultaneously requiring ultra-low power and small size. The proposed ADC is based on the conventional algorithmic architecture with a recycling signal path to optimize sampling rate, resolution, chip area, and power consumption. The input SHA with eight input channels employs a folded-cascode amplifier to achieve a required DC gain and a high phase margin. A 3-D fully symmetric layout with critical signal lines shielded reduces the capacitor and device mismatch of the multiplying D/A converter while switched-bias power-reduction circuits minimize the power consumption of analog amplifiers. Current and voltage references are integrated on chip with optional off-chip voltage references for low glitch noise. The down-sampling clock signal selects the sampling rate of 200 kS/s and 10 kS/s with a further reduced power depending on applications. The prototype ADC in a 0.18 µm n-well 1P6M CMOS process demonstrates a maximum measured DNL and INL within 0.40 LSB and 1.97 LSB and shows a maximum SNDR and SFDR of 55 dB and 70 dB at all sampling frequencies up to 200 kS/s, respectively. The ADC occupies an active die area of 0.47 mm2 and consumes 0.94 mW at 200 kS/s and 0.63 mW at 10 kS/s with a 1.8 V supply.

Combination of mutually complementary features is necessary to cope with various changes in pattern classification between normal and pathological voices. This paper proposes a method to improve pathological/normal voice classification performance by combining heterogeneous features. Different combinations of auditory-based and higher-order features are investigated. Their performances are measured by Gaussian mixture models (GMMs), linear discriminant analysis (LDA), and a classification and regression tree (CART) method. The proposed classification method by using the CART analysis is shown to be an effective method for pathological voice detection, with a 92.7% classification performance rate. This is a noticeable improvement of 54.32% compared to the MFCC-based GMM algorithm in terms of error reduction.

The HITS algorithm proposed by Kleinberg is one of the representative methods of scoring Web pages by using hyperlinks. In the days when the algorithm was proposed, most of the pages given high score by the algorithm were really related to a given topic, and hence the algorithm could be used to find related pages. However, the algorithm and the variants including Bharat's improved HITS, abbreviated to BHITS, proposed by Bharat and Henzinger cannot be used to find related pages any more on today's Web, due to an increase of spam links. In this paper, we first propose three methods to find "linkfarms," that is, sets of spam links forming a densely connected subgraph of a Web graph. We then present an algorithm, called a trust-score algorithm, to give high scores to pages which are not spam pages with a high probability. Combining the three methods and the trust-score algorithm with BHITS, we obtain several variants of the HITS algorithm. We ascertain by experiments that one of them, named TaN+BHITS using the trust-score algorithm and the method of finding linkfarms by employing name servers, is most suitable for finding related pages on today's Web. Our algorithms take time and memory no more than those required by the original HITS algorithm, and can be executed on a PC with a small amount of main memory.

In this paper, we study a problem of inferring blood relationships which satisfy a given matrix of genetic distances between all pairs of n nodes. Blood relationships are represented by our proposed graph class, which is called a pedigree graph. A pedigree graph is a directed acyclic graph in which the maximum indegree is at most two. We show that the number of pedigree graphs which satisfy the condition of given genetic distances may be exponential, but they can be represented by one directed acyclic graph with n nodes. Moreover, an O(n3) time algorithm which solves the problem is also given. Although phylogenetic trees and phylogenetic networks are similar data structures to pedigree graphs, it seems that inferring methods for phylogenetic trees and networks cannot be applied to infer pedigree graphs since nodes of phylogenetic trees and networks represent species whereas nodes of pedigree graphs represent individuals. We also show an O(n2) time algorithm which detects a contradiction between a given pedigree graph and distance matrix of genetic distances.

In this letter, a computational approach for solving cross-coupled algebraic Riccati equations (CAREs) is investigated. The main purpose of this letter is to propose a new algorithm that combines Newton's method with a gradient-based iterative (GI) algorithm for solving CAREs. In particular, it is noteworthy that both a quadratic convergence under an appropriate initial condition and reduction in dimensions for matrix computation are both achieved. A numerical example is provided to demonstrate the efficiency of this proposed algorithm.

When a store sells items to customers, the store wishes to decide the prices of the items to maximize its profit. If the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. It would be hard for the store to decide the prices of items. Assume that a store has a set V of n items and there is a set C of m customers who wish to buy those items. The goal of the store is to decide the price of each item to maximize its profit. We refer to this maximization problem as an item pricing problem. We classify the item pricing problems according to how many items the store can sell or how the customers valuate the items. If the store can sell every item i with unlimited (resp. limited) amount, we refer to this as unlimited supply (resp. limited supply). We say that the item pricing problem is single-minded if each customer j ∈ C wishes to buy a set ej ⊆ V of items and assigns valuation w(ej) ≥ 0. For the single-minded item pricing problems (in unlimited supply), Balcan and Blum regarded them as weighted k-hypergraphs and gave several approximation algorithms. In this paper, we focus on the (pseudo) degree of k-hypergraphs and the valuation ratio, i.e., the ratio between the smallest and the largest valuations. Then for the single-minded item pricing problems (in unlimited supply), we show improved approximation algorithms (for k-hypergraphs, general graphs, bipartite graphs, etc.) with respect to the maximum (pseudo) degree and the valuation ratio.