In this paper we study the problem of how to identify multiple disjoint paths that have the minimum total cost OPT and satisfy a delay bound D in a graph G. This problem has lots of applications in networking such as fault-tolerant quality of service (QoS) routing and network-flow load balancing. Recently, several approximation algorithms have been developed for this problem. Here, we propose a new approximation algorithm for it by using the Lagrangian Relaxation method. We then present a simple approximation algorithm for finding multiple link-disjoint paths that satisfy the delay constraints at a reasonable total cost. If the optimal solution under delay-bound D has a cost OPT, then our algorithm can find a solution whose delay is bounded by (1+)D and the cost is no more than (1+k)OPT. The time complexity of our algorithm is much better than the previous algorithms.

Software defined radio, which uses reconfigurable signal processing devices, requires the determination of multiple unknown parameters to realize the potential capabilities of adaptive communication. Evolutional algorithms are optimal multi dimensional search techniques, and are well known to be effective for parameter determination. This letter proposes an evolutional algorithm for learning the mobile time-varying channel parameters without any specific assumption of scattering distribution. The proposed method is very simple to realize, but can provide precise channel estimation results. Simulations of an OFDM system show that for an example of OFDM communication under the time-varying fading channel, the proposed learning method can achieve the better BER performance.

This paper presents a formal design of arithmetic circuits using an arithmetic description language called ARITH. The key idea in ARITH is to describe arithmetic algorithms directly with high-level mathematical objects (i.e., number representation systems and arithmetic operations/formulae). Using ARITH, we can provide formal description of arithmetic algorithms including those using unconventional number systems. In addition, the described arithmetic algorithms can be formally verified by equivalence checking with formula manipulations. The verified ARITH descriptions are easily translated into the equivalent HDL descriptions. In this paper, we also present an application of ARITH to an arithmetic module generator, which supports a variety of hardware algorithms for 2-operand adders, multi-operand adders, multipliers, constant-coefficient multipliers and multiply accumulators. The language processing system of ARITH incorporated in the generator verifies the correctness of ARITH descriptions in a formal method. As a result, we can obtain highly-reliable arithmetic modules whose functions are completely verified at the algorithm level.

This paper presents an algorithm-level interpretation of fast adder structures in binary/multiple-valued logic. The key idea is to employ a unified representation of addition algorithms called Counter Tree Diagrams (CTDs). The use of CTDs makes it possible to describe and analyze addition algorithms at various levels of abstraction. A high-level CTD represents a network of coarse-grained components associated with multiple-valued logic devices, while a low-level CTD represents a network of primitive components directly mapped onto binary logic devices. The level of abstraction in circuit representation can be changed by decomposition of CTDs. We can derive possible variations of adder structures by decomposing a high-level CTD into low-level CTDs. This paper demonstrates the interpretation of redundant arithmetic adders based on CTDs. We first introduce an extension of CTDs to represent possible redundant arithmetic adders with limited carry propagation. Using the extended version of CTDs, we can classify the conventional adder structures including those using emerging devices into three types in a systematic way.

In this paper, we present a scheduler that incorporates round robin service within a VirtualClock discipline. Time-stamp based scheduling algorithms attain a low local delay bound and performance guarantee, but are computationally complex. On the other hand, round robin schemes are simple to implement and have computational complexity of O(1), but they are well known for their output burstiness and short-term unfairness. In order to overcome this problem, we combine round robin with VirtualClock in an algorithm we call VCRR. VCRR possesses better fairness than simple round robin, low jitter and a good scheduling delay bound. At the same time, VCRR preserves the O(1) time complexity of round robin. Simulation experiments show VCRR's efficiency in terms of delay performance, jitter and fairness.

Petri nets with inhibitor arcs are referred to as inhibitor-arc Petri nets. It is shown that modeling capability of inhibitor-arc Petri nets is equivalent to that of Turing machines. The subject of this paper is the legal firing sequence problem (INLFS) for inhibitor-arc Petri nets: given an inhibitor-arc Petri net IN, an initial marking M0 and a firing count vector X, find a firing sequence δ such that its firing starts from M0 and each transition t appears in δ exactly X(t) times as prescribed by X. The paper is the first step of research for time complexity analysis and designing algorithms of INLFS, one of the most fundamental problems for inhibitor-arc Petri nets having more modeling capability than ordinary Peri nets. The recognition version of INLFS, denoted as RINLFS, means a decision problem, asking a "yes" or "no" answer on the existence of a solution δ to INLFS. The main results are the following (1) and (2). (1) Proving (1-1) and (1-2) when the underlying Petri net of IN is an unweighted state machine: (1-1) INLFS can be solved in pseudo-polynomial (O(|X|)) time for IN of non-adjacent type having only one special place called a rivet; (1-2) RINLFS is NP-hard for IN with at least three rivets; (2) Proving that RINLFS for IN whose underlying Petri net is unweighted and forward conflict-free is NP-hard. Heuristic algorithms for solving INLFS are going to be proposed in separate papers.

The family of Quasi-Additive (QA) algorithms is a natural generalization of the perceptron learning, which is a kind of on-line learning having two parameter vectors: One is an accumulation of input vectors and the other is a weight vector for prediction associated with the former by a nonlinear function. We show that the vectors have a dually-flat structure from the information-geometric point of view, and this representation makes it easier to discuss the convergence properties.

In this paper, we give an algorithm for the node-to-set disjoint paths problem in a transposition graph. The algorithm is of polynomial order of n for an n-transposition graph. It is based on recursion and divided into two cases according to the distribution of destination nodes. The maximum length of each path and the time complexity of the algorithm are estimated theoretically to be O(n7) and 3n - 5, respectively, and the average performance is evaluated based on computer experiments.

Design of optimal controllers satisfying performance criteria of minimum tracking error and disturbance level for an interval system using a multi-objective evolutionary approach is proposed in this paper. Based on a worst-case design philosophy, the design problem is formulated as a minimax optimization problem, subsequently solved by a proposed two-phase multi-objective genetic algorithm (MOGA). By using two sets of interactive genetic algorithms where the first one determines the maximum (worst-case) cost function values for a given set of controller parameters while the other one minimizes the maximum cost function values passed from the first genetic algorithm, the proposed approach evolutionarily derives the optimal controllers for the interval system. To suitably assess chromosomes for their fitness in a population, root locations of the 32 generalized Kharitonov polynomials will be used to establish a constraints handling mechanism, based on which a fitness function can be constructed for effective evaluation of the chromosomes. Because of the time-consuming process that genetic algorithms generally exhibit, particularly the problem nature of minimax optimization, a parallel computation scheme for the evolutionary approach in the MATLAB-based working environment is also proposed to accelerate the design process.

We present a novel, simple, efficient algorithm to generate random samples uniformly on the directional space of a cone. This algorithm has three advantages over the conventional non-uniform approach. First, to the best of our knowledge, this algorithm is original for uniformly sampling smaller areas of cones. Second, it is faster. Third, it always generates valid samples, which is not possible for the conventional approach.

An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio for an arbitrarily positive constant c, where N denotes the number of men in an input.

This paper deals with questions concerning the supply of building-blocks (BBs) in the initial population of real-coded genetic algorithms (rGAs). Drawing upon the methodology of existing BB supply studies for finite alphabets, facetwise models for the supply of a single schema as well as for the supply of all the schemata in a partition are proposed. A model for the initial population size necessary to ensure the presence of all the raw BBs with a given supply error has also been developed using the partition success model. Experimental results show the effectiveness of the facetwise models and the initial population sizing model. Finally, an adaptation approach is suggested for practical use of the BB supply.

We extend the adaptive-order rational Arnoldi algorithm for multiple-inputs and multiple-outputs (MIMO) interconnect model order reductions. Instead of using the standard Arnoldi algorithm for the SISO adaptive-order reduction algorithm (AORA), we study the adaptive-order rational global Arnoldi (AORGA) algorithm for MIMO model reductions. In this new algorithm, the input matrix is treated as a vector form. A new matrix Krylov subspace, generated by the global Arnoldi algorithm, will be developed by a Frobenius-orthonormal basis. By employing congruence transformation with the matrix Krylov subspace, the one-sided projection method can be used to construct a reduced-order system. It will be shown that the system moment matching can be preserved. In addition, we also show that the transfer matrix residual error of the reduced system can be derived analytically. This error information will provide a guideline for the order selection scheme. The algorithm can also be applied to the classical multiple point MIMO Pade approximation by the rational Arnoldi algorithm for multiple expansion points. Experimental results demonstrate the feasibility and the effectiveness of the proposed method.

We consider the classification problem to construct a classifier c:{0,1}n{0,1} from a given set of examples (training set), which (approximately) realizes the hidden oracle y:{0,1}n{0,1} describing the phenomenon under consideration. For this problem, a number of approaches are already known in computational learning theory; e.g., decision trees, support vector machines (SVM), and iteratively composed features (ICF). The last one, ICF, was proposed in our previous work (Haraguchi et al., (2004)). A feature, composed of a nonempty subset S of other features (including the original data attributes), is a Boolean function fS:{0,1}S{0,1} and is constructed according to the proposed rule. The ICF algorithm iterates generation and selection processes of features, and finally adopts one of the generated features as the classifier, where the generation process may be considered as embodying the idea of boosting, since new features are generated from the available features. In this paper, we generalize a feature to an extended Boolean function fS:{0,1,*}S{0,1,*} to allow partial knowledge, where * denotes the state of uncertainty. We then propose the algorithm ICF* to generate such generalized features. The selection process of ICF* is also different from that of ICF, in that features are selected so as to cover the entire training set. Our computational experiments indicate that ICF* is better than ICF in terms of both classification performance and computation time. Also, it is competitive with other representative learning algorithms such as decision trees and SVM.

The present letter deals with the blind equalization problem of a single-input single-output infinite impulse response (SISO-IIR) channel with additive Gaussian noise. To solve the problem, we propose a new criterion for maximizing constrainedly a fourth-order cumulant. The algorithms derived from the criterion have such a novel property that even if Gaussian noise is added to the output of the channel, an effective zero-forcing (ZF) equalizer can be obtained with as little influence of Gaussian noise as possible. To show the validity of the proposed criterion, some simulation results are presented.

A naive coding of floorplans needs 2m bits for each floorplan. In this paper we give a new simple coding of floorplans, which needs only 5m/3 bits for each floorplan.

A radio network (RN for short) is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations run on batteries and expends power while broadcasting/receiving a data packet. Thus, the most important measure to evaluate protocols on the radio network is the number of awake time slots, in which a station is broadcasting/receiving a data packet. We also assume that the stations are identical and have no unique ID number, and no station knows the number n of the stations. For given n keys one for each station, the ranking problem asks each station to determine the number of keys in the RN smaller than its own key. The main contribution of this paper is to present an optimal randomized ranking protocol on the k-channel RN. Our protocol solves the ranking problem, with high probability, in O(+log n) time slots with every station being awake for at most O(log n) time slots. We also prove that any randomized ranking protocol is required to run in expected Ω(+log n) time slots with at least one station being awake for expected Ω(log n) time slots. Therefore, our ranking protocol is optimal.

In this work we present an energy efficient leader election protocol for anonymous radio network populated with n mobile stations. Previously, Nakano and Olariu have presented a leader election protocol that terminates, with probability exceeding 1- (f ≥ 1), in log log n+o(log log n)+O(log f) time slots [14]. As the above protocol works under the assumption that every station has the ability to transmit and monitor the channel at the same time, it requires every station to be equipped with two transceivers. This assumption, however, is unrealistic for most mobile stations due to constraints in cost, size, and energy dissipation. Our main contribution is to show that it is possible to elect a leader in an anonymous radio network where each station is equipped with a single transceiver. Quite surprisingly, although every station has only one transceiver, our leader election protocol still runs, with probability exceeding 1- (f ≥ 1), in log log n+o(log log n)+O(log f) time slots. Moreover, our leader election protocol needs only expected O(n) total awake time slots, while Nakano and Olariu's protocol needs expected O(nlog log n) total awake time slots. Since every leader election protocol needs at least Ω(n) awake time slots, our leader election protocol is optimal in terms of the expected awake time slots.

The aim of this research is the efficient cryptanalysis of the Shrinking Generator through its characterization by means of Linear Hybrid Cellular Automata. This paper describes a new known-plaintext attack based on the computation of the characteristic polynomials of sub-automata and on the generation of the Galois field associated to one of the Linear Feedback Shift Registers components of the generator. The proposed algorithm allows predicting with absolute certainty, many unseen bits of the keystream sequence, thanks to the knowledge of both registers lengths, the characteristic polynomial of one of the registers, and the interception of a variable number of keystream bits.

Ants-based routing algorithms have attracted the attention of researchers because they are more robust, reliable, and scalable than other conventional routing algorithms. Since they do not involve extra message exchanges to maintain paths when network topology changes, they are suitable for mobile ad-hoc networks where nodes move dynamically and topology changes frequently. As the number of nodes increases, however, the number of ants (i.e., mobile agents or control messages) also increases, which means that existing algorithms have poor scalability. In this paper, we propose a scalable ant-based routing algorithm that keeps the overhead low while keeping paths short. Our algorithm uses a multistep TTL (Time To Live) scheme, an effective message migration scheme, and an efficient scheme for updating the probability of packet forwarding. Simulation experiments have confirmed that our proposed algorithm can establish shorter paths than the conventional ant-based algorithm with the same signaling overhead.