Cowen gave a universal compact routing algorithm with a stretch factor of three and table-size of O(n2/3log4/3n) based on a simple and practical model. (The table-size is later improved to O(n1/2log3/2n).) This paper considers, using the same model, how the necessary table-size differs if the stretch factor must be less than three. It is shown that: (i) There is a routing algorithm with a stretch factor of two whose table-size is (n -+ 2)log n. (ii) There is a network for which any routing algorithm that follows the model and with a stretch factor of less than three needs a table-size of (n - 2)log n in at least one node. Thus, we can only reduce roughly an additive log n (i.e., table-entries) from the trivial table-size of n log n which obviously enables shortest-path routing. Furthermore it turns out that we can reduce only an additive log n (i.e., only one table-entry) from the trivial n log n if we have to achieve a stretch factor of less than two. Thus the algorithm (i) is (roughly) tight both in its stretch factor and in its table-size.

In this work we give an extension of Kauffman's NK-Landscapes to multiobjective MNK-Landscapes in order to study the effects of epistasis on the performance of multiobjective evolutionary algorithms (MOEAs). This paper focuses on the development of multiobjective random one-bit climbers (moRBCs). We incrementally build several moRBCs and analyze basic working principles of state of the art MOEAs on landscapes of increased epistatic complexity and number of objectives. We specially study the effects of Pareto dominance, non-dominance, and the use of memory and a population to influence the search. We choose an elitist non-dominated sorting multiobjective genetic algorithm (NSGA-II) as a representative of the latest generation of MOEAs and include its results for comparison. We detail the behavior of the climbers and show that population based moRBCs outperform NSGA-II for all values of M and K.

In this paper, we consider a data mining problem for semi-structured data. Modeling semi-structured data as labeled ordered trees, we present an efficient algorithm for discovering frequent substructures from a large collection of semi-structured data. By extending the enumeration technique developed by Bayardo (SIGMOD'98) for discovering long itemsets, our algorithm scales almost linearly in the total size of maximal tree patterns contained in an input collection depending mildly on the size of the longest pattern. We also developed several pruning techniques that significantly speed-up the search. Experiments on Web data show that our algorithm runs efficiently on real-life datasets combined with proposed pruning techniques in the wide range of parameters.

In this paper, an adaptive bound reduced-form genetic algorithm (ABRGA) to tune the control points of B-spline neural networks is proposed. It is developed not only to search for the optimal control points but also to adaptively tune the bounds of the control points of the B-spline neural networks by enlarging the search space of the control points. To improve the searching speed of the reduced-form genetic algorithm (RGA), the ABRGA is derived, in which better bounds of control points of B-spline neural networks are determined and paralleled with the optimal control points searched. It is shown that better efficiency is obtained if the bounds of control points are adjusted properly for the RGA-based B-spline neural networks.

Nonminimum phase systems are difficult to be controlled with a conventional PID-type controller because of their inherent characteristics of undershooting. A neuro-controller combined with a PID-type controller has been shown to improve the control performance of the nonminimum phase systems while maintaining stability. In this paper, we apply a multiobjective evolutionary optimization method for training the neuro-controller to reduce the undershooting of the nonminimum phase system. The computer simulation shows that the proposed multiobjective approach is very effective and suitable because it can minimize the control error as well as reduce undershooting and chattering. This method can be applied to many industrial nonminimum phase problems with ease.

Malignant melanoma is a skin cancer that can be mistaken as a harmless mole in the early stages and is curable only in these early stages. Therefore, dermatologists use a microscope that shows the pigment structures of the skin to classify suspicious skin lesions as malignant or benign. This microscope is called "dermoscope." However, even when using a dermoscope a malignant skin lesion can be mistaken as benign or vice versa. Therefore, it seems desirable to analyze dermoscopic images by computer to classify the skin lesion. Before a dermoscopic image can be classified, it should be segmented into regions of the same color. For this purpose, we propose a segmentation method that automatically determines the number of colors by optimizing a cluster validity index. Cluster validity indices can be used to determine how accurately a partition represents the "natural" clusters of a data set. Therefore, cluster validity indices can also be applied to evaluate how accurately a color image is segmented. First the RGB image is transformed into the L*u*v* color space, in which Euclidean vector distances correspond to differences of visible colors. The pixels of the L*u*v* image are used to train a self-organizing map. After completion of the training a genetic algorithm groups the neurons of the self-organizing map into clusters using fuzzy c-means. The genetic algorithm searches for a partition that optimizes a fuzzy cluster validity index. The image is segmented by assigning each pixel of the L*u*v* image to the nearest neighbor among the cluster centers found by the genetic algorithm. A set of dermoscopic images is segmented using the method proposed in this research and the images are classified based on color statistics and textural features. The results indicate that the method proposed in this research is effective for the segmentation of dermoscopic images.

The availability of a low cost hardware has increased the development of distributed systems, by making then more and more accessible. In order to optimize the resources allocation on the distributed systems, some load balancing algorithms have been proposed. These algorithms distribute the application loads over the environment computers, make homogeneous the occupation of the whole environment and increase the application performance. This equal distribution prevents certain computers to get overloaded, to the detriment of the idleness of the other ones. This article proposes and analyzes the TLBAGrid, a load balancing algorithm for Grid computing environments.

Graph data in large scientific/engineering applications are often too massive to fit inside the computer's main memory. The resulting input/output (I/O) costs could be a major performance bottleneck. This paper proposes an extension to extant multilevel graph partitioning algorithms with improved I/O-efficiency. The input graph is envisioned as the union of disjoint blocks (subgraphs) of almost the same size. Each block is coarsened in turn. Recursive matching and contraction are the operations in this phase. All the coarsened blocks are then merged in an iterative manner in order to ensure that the resulting graph fits in the main memory. This graph is then treated with an in-core multilevel graph partitioning algorithm in the usual way. Our experimental results show that the larger graph size is, the more dependent on the I/O-efficiency the performance is. And our modification can easily partition very large graphs. It also exhibits considerable improvement in I/O-complexity.

In this paper we consider the Feedback-Guided Dynamic Loop Scheduling (FGDLS) method that was proposed by Bull. The method uses a feedback-guided mechanism to schedule a parallel loop within a sequential outer loop. The execution times and the scheduling bounds at a outer iteration are used to find the scheduling bound of the next outer iteration. In this way FGDLS achieves an optimal load balance. Two algorithms have been proposed so far by Tabirca et al. In this article we will review these two algorithms and will give a comparison between their performances.

The alignment of biological sequences is a crucial tool in molecular biology and genome analysis. A wide variety of approaches has been proposed for multiple sequence alignment problem; however, some of them need prerequisites to help find the best alignment or some of them may suffer from the drawbacks of complexity and memory requirement so they can be only applied to cases with a limited number of sequences. In this paper, we view the multiple sequence alignment problem as an optimization problem and propose a heuristic-based genetic algorithm (GA) approach to solve it. The heuristic/GA hybrid yields better results than other well-known packages do. Experimental results are presented to illustrate the feasibility of the proposed approach.

This paper proposes several novel hierarchical interconnection networks based on the (3, 3)-graphs, namely folded (3, 3)-networks, root-folded (3, 3)-networks, recursively expanded (3, 3)-networks, and flooded (3, 3)-networks. Just as the hypercubes, CCC, Peterson-based networks, and Heawood-based networks, these hierarchical networks have the following nice properties: regular topology, high scalability, and small diameters. Due to these important properties, these hierarchical networks seem to have the potential as alternatives for the future interconnection structures of multicomputer systems, especially massively parallel processors (MPPs). Furthermore, this paper will present the routing and broadcasting algorithms for these proposed networks to demonstrate that these algorithms are as elegant as the algorithms for hypercubes, CCC, and Petersen- or Heawood-based networks.

This paper proposes the use of the ratio of wavelet extrema numbers taken from the horizontal and vertical counts respectively as a texture feature, which is called aspect ratio of extrema number (AREN). We formulate the classification problem upon natural and synthesized texture images as an optimization problem and develop a coevolving approach to select both scalar wavelet and multiwavelet feature spaces of greater discriminatory power. Sequential searches and genetic algorithms (GAs) are comparatively investigated. The experiments using wavelet packet decompositions with the innovative packet-tree selection scheme ascertain that the classification accuracy of coevolutionary genetic algorithms (CGAs) is acceptable enough.

Sampling is important for many applications in research areas such as graphics, vision, and image processing. In this paper, we present a novel stratified sampling algorithm (SSA) for the coiled tubing surface with a given probability density function. The algorithm is developed from the inverse function of the integration for the areas of the coiled tubing surface. We exploit a Hierarchical Allocation Strategy (HAS) to preserve sample stratification when generating any desirable sample numbers. This permits us to reduce variances when applying our algorithm to Monte Carlo Direct Lighting for realistic image generation. We accelerate the sampling process using a segmentation technique in the integration domain. Our algorithm thus runs 324 orders of magnitude faster when using faster SSA algorithm where the order of the magnitude is proportional to the sample numbers. Finally, we employ a parabolic interpolation technique to decrease the average errors occurred for using the segmentation technique. This permits us to produce nearly constant average errors, independent of the sample numbers. The proposed algorithm is novel, efficient in computing and feasible for realistic image generation using Monte Carlo method.

Cryptography and Coding Theory are closely related in many respects. Recently, the problem of "decoding Reed Solomon codes" (also known as "polynomial reconstruction") was suggested as an intractability assumption to base the security of protocols on. This has initiated a line of cryptographic research exploiting the rich algebraic structure of the problem and its variants. In this paper we give a short overview of the recent works in this area as well as list directions and open problems in Polynomial Reconstruction Based Cryptography.

In this paper, we explore a method to the problem of spoken document categorization, which is the task of automatically assigning spoken documents into a set of predetermined categories. To categorize spoken documents, subword unit representations are used as an alternative to word units generated by either keyword spotting or large vocabulary continuous speech recognition (LVCSR). An advantage of using subword acoustic unit representations to spoken document categorization is that it does not require prior knowledge about the contents of the spoken documents and addresses the out of vocabulary (OOV) problem. Moreover, this method works in reliance on the sounds of speech rather than exact orthography. The use of subword units instead of words allows approximate matching on inaccurate transcriptions, makes "sounds-like" spoken document categorization possible. We also explore the performance of our method when the training set contains both perfect and errorful phonetic transcriptions, and hope the classifiers can learn from the confusion characteristics of recognizer and pronunciation variants of words to improve the robustness of whole system. Our experiments based on both artificial and real corrupted data sets show that the proposed method is more effective and robust than the word based method.

In the CNN problem, a "scene" appears on the two-dimensional plane, at different positions sequentially, and a "camera crew" has to shoot the scene whenever it appears. If a scene appears at some position, the camera crew does not have to move to the position exactly, but has only to move to a point that lies in the same horizontal or vertical line with the scene. Namely it is enough to move either to the same row or to the same column. The goal is to minimize the total moving distance of the camera crew. This problem has been quite popular in the last decade but it is still open whether or not there is a competitive algorithm, i.e., an algorithm with competitive ratio bounded by a constant. In this paper we study this problem under a natural restriction that the server can move only along the X-axis and the Y-axis. It is shown that there exists a competitive algorithm for this restricted version, namely there is an online algorithm for this "axis-bound CNN" with competitive ratio 9.0.

The number and location of the inventory centers play an important role in the material distribution process since residents and inventory centers may be in dispersed regions. In this paper, we view the problem of finding the better locations for the inventory centers as an optimization problem, and propose a nested genetic algorithm (NGA) approach to design an optimal material distribution system. We demonstrate the feasibility of the proposed approach by numerical experiments.

The capabilities of reliable computations in one-dimensional cellular automata are investigated by means of the Early Bird Problem. The problem is typical for situations in massively parallel systems where a global behavior must be achieved by only local interactions between the single elements. The cells that cause the misoperations are assumed to behave as follows. They run a self-diagnosis before the actual computation once. The result is stored locally such that the working state of a cell becomes visible to its neighbors. A non-working (defective) cell cannot modify information but is able to transmit it unchanged with unit speed. We present an O(n log (n) log (n))-time fault-tolerant solution of the Early Bird Problem.

Group mutual exclusion is an interesting generalization of the mutual exclusion problem. This problem was introduced by Joung, and some algorithms for the problem have been proposed by incorporating mutual exclusion algorithms. Group mutual exclusion occurs naturally in a situation where a resource can be shared by processes of the same group, but not by processes of a different group. It is also called the congenial talking philosophers problem. In this paper we propose two algorithms based on ticket orders for the group mutual exclusion problem on the asynchronous shared memory model. These algorithms are some modifications of the Bakery algorithm. They satisfy lockout freedom and a high degree of concurrency performance. Each of these algorithms uses single-writer shared variables together with two multi-writer shared variables that are never concurrently written. One of these algorithms has another desirable property, called smooth admission. By this property, during the period that the resource is occupied by the leader (called the chair), a process wishing to join the same group as the leader's group can be granted use of the resource in constant time.

This paper presents a strictly time- and communication-optimal distributed sorting algorithm in a line network. A strictly time-optimal distributed sorting algorithm in a line network has already been designed. However, its communication complexity is not strictly optimal and it seems to be difficult to extend it to other problems, such as that related to multiple elements in a process, and also the dynamic sorting problem where the number of elements each process should have as its solution is not the same as that in the initial state. Therefore, the algorithm in this paper was designed by an alternative approach to make it strictly time- and communication-optimal. Moreover, an extension to the dynamic sorting problem is described.