Search

In this paper, we study a discrete momentum consensus-based optimization (Momentum-CBO) algorithm which corresponds to a second-order generalization of the discrete first-order CBO [S.-Y. Ha, S. Jin and D. Kim, Convergence of a first-order consensus-based global optimization algorithm, Math. Models Methods Appl. Sci. 30 (2020) 2417–2444]. The proposed algorithm can be understood as the modification of ADAM-CBO, replacing the normalization term by unity. For the proposed Momentum-CBO, we provide a sufficient framework which guarantees the convergence of algorithm toward a global minimum of the objective function. Moreover, we present several experimental results showing that Momentum-CBO has an improved success rate of finding the global minimum compared to vanilla-CBO and show the stability of Momentum-CBO under different initialization schemes. We also show that Momentum-CBO can be used as the alternative of ADAM-CBO which does not have a proper convergence analysis. Finally, we give an application of Momentum-CBO for Lyapunov function approximation using symbolic regression techniques. [ABSTRACT FROM AUTHOR]

[M. Ma, The connectivity of exchanged hypercubes, Discrete Math., Algorithms Appl. 2(2) (2010) 213–220.] proved that the vertex connectivity and the edge connectivity of the exchanged hypercube are each equal to the minimum degree of the graph. This paper presents a proof of that result, which is substantially simpler and more intuitive. [ABSTRACT FROM AUTHOR]

It has been suggested in the literature that ordinary finite-precision floating-point arithmetic is inadequate for geometric computation, and that researchers in numerical analysis may believe that the difficulties of error in geometric computation can be overcome by simple approaches. It is the purpose of this paper to show that these suggestions, based on an example showing failure of a certain algorithm for computing planar convex hulls, are misleading, and why this is so. It is first shown how the now-classical backward error analysis can be applied in the area of computational geometry. This analysis is relevant in the context of uncertain data, which may well be the practical context for computational-geometry algorithms such as, say, those for computing convex hulls. The exposition will illustrate the fact that the backward error analysis does not pretend to overcome the problem of finite precision: it merely provides a way to distinguish those algorithms that overcome the problem to whatever extent it is possible to do so. It is then shown that often the situation in computational geometry is exactly parallel to other areas, such as the numerical solution of linear equations, or the algebraic eigenvalue problem. Indeed, the example mentioned can be viewed simply as an example of the use of an unstable algorithm, for a problem for which computational geometry has already discovered provably stable algorithms. Finally, the paper discusses the implications of these analyses for applications in three-dimensional solid modeling. This is done by considering a problem defined in terms of a simple extension of the planar convex-hull algorithm, namely, the verification of the well-formedness of extruded objects. A brief discussion concerning more difficult problems in solid modeling is also included. [ABSTRACT FROM AUTHOR]

In this paper we discuss two modifications of the surrogate data method based on phase randomization, see [Theiler et al., 1992]. By construction, phase randomized surrogates are circular stationary. In this respect they differ from the original time series. This can cause level inaccuracies of surrogate data tests. We will illustrate this. These inaccuracies are caused by end to end mismatches of the original time series. In this paper we will discuss two approaches to remedy this problem: resampling from subsequences without end to end mismatches and data tapering. Both methods can be understood as attempts to make non-circular data approximately circular. We will show that the first method works quite well for a large range of applications whereas data tapering leads only to improvements in some examples but can be very unstable otherwise. [ABSTRACT FROM AUTHOR]

The longest common subsequence is a well known and popular method for measuring similarity between sequences. It advocates the use of information contained in the longest common subsequence as an indication of similarity. In this paper we consider the count of all common subsequences as a measure of sequence similarity with the view that all common information is captured. This measure is inspired and derived from a generic similarity measure, neighborhood counting metric. The close connection of the neighborhood counting metric with probability and the Bayes classifier helps gain an insight from the probabilistic perspective into the all-common subsequences measure. We design algorithms to calculate this measure and we also carry out an experiment in the framework of k-nearest neighbors on a gene sequence classification task. The experiment shows that the all-common subsequences measure and the longest common subsequence measure have little difference for small k values, but differ significantly for large k values. The performance of the all-common subsequences measure remains steady as k gets larger, but the performance of the longest common subsequence measure drops sharply as k gets larger. Such a property may be useful for those tasks where we are interested not only in the nearest neighbor, but also in the first k nearest neighbors. The main contribution of this paper is a suite of algorithms for finding all common subsequences. [ABSTRACT FROM AUTHOR]

In this paper, we discuss a simple, Monte Carlo algorithm for the problem of checking whether a Quantified Boolean Formula (QBF) in Conjunctive Normal Form (CNF), with at most two literals per clause has a model. The term k-CNF is used to describe boolean formulas in CNF, with at most /c literals per clause and the problem of checking whether a given k-CNF formula is satisfiable is called the k-SAT problem. A QBF is a boolean formula, accompanied by a quantifier string which imposes a linear ordering on the variables of that formula. The problem of finding a model for a QBF formula in CNF, with at at most k literals per clause is called the QkSAT problem. The QkSAT problem is PSPACE-complete, for k ≥ 3. However, the Q2SAT problem can be decided in polynomial time; the graph-based procedure, discussed in [1], is the first such algorithm for this problem. This procedure requires the construction of a global implication graph, corresponding to the input formula and searching for certain paths in this graph. Hence the complete set of clauses must be part of the input. We propose an incremental, randomized approach for the Q2SAT problem that is essentially local in nature, in that the complete clausal set need not be provided at any time, in the presence of a verifier. We show that the randomized algorithm can be analyzed as a one-dimensional random walk, with one reflecting barrier and one absorbing barrier. On a Q2SAT instance with in clauses on n variables, our coin-flipping algorithm runs in time O(n² V(m, n)), where V(m, n) is the time required to verify that a given model satisfies the formula. Additionally, if the instance is satisfiable, the probability that our algorithm fails to find a model is less than one half. The design and analysis of a randomized algorithm for a problem, is important from both the theoretical and the practical perspectives. Randomized approaches tend to be simple and elegant, thereby making the process of checking correctness, effortless as well. The randomized approach discussed in this paper lays the groundwork for analyzing a number of problems related to 2CNF formulas and directed graphs. We remark that our work in this paper is the first randomized algorithm for a class of QBFs. [ABSTRACT FROM AUTHOR]

This paper studies the two-dimensional range search problem, and constructs a simple and efficient algorithm based on the Voronoi diagram. In this problem, a set of points and a query range are given, and we want to enumerate all the points which are inside the query range as quickly as possible. In most of the previous researches on this problem, the shape of the query range is restricted to particular ones such as circles, rectangles and triangles, and the improvement on the worst-case performance has been pursued. On the other hand, the algorithm proposed in this paper is designed for a general shape of the query range in the two-dimensional space, and is intended to accomplish a good average-case performance. This performance is actually observed by numerical experiments. In these experiments, we compare the execution time of the proposed algorithm with those of other representative algorithms such as those based on the bucketing technique and the k-d tree. We can observe that our algorithm shows the better performance in almost all the cases. [ABSTRACT FROM AUTHOR]

This paper proposes a procedure to design fault tolerant algorithms for the R-Mesh and some of its restrictive variations. This procedure first identifies a healthy sub-mesh from a faulty model using the bypass and removal fault model. Then it uses scalable algorithms to simulate the larger faulty model on the resulting healthy sub-mesh. The algorithms for the bypass model tolerates n faults in an n×n R-Mesh (LR-Mesh) and runs in O(T log n) (O(T)) time, where T is the execution time on the original mesh without faults. For the removal model, we design fault tolerant algorithms for some interesting variations of the R-Mesh, specifically, the NXR-Mesh and the NXLR-Mesh. We propose the first scaling simulations for these models and present a simulation of the R-Mesh on the NXR-Mesh. The results of this paper enable us to consider certain reconfigurable models in a more practical environment than previously allowed. [ABSTRACT FROM AUTHOR]

There is strong empirical evidence that human perception of a graph drawing is negatively correlated with the number of edge crossings. However, recent experiments show that one can reduce the negative effect by ensuring that the edges that cross do so at large angles. These experiments have motivated a number of mathematical and algorithmic studies of 'right angle crossing (RAC)' drawings of graphs, where the edges cross each other perpendicularly. In this paper we give an algorithm for constructing RAC drawings of 'outer-1-plane' graphs, that is, topological graphs in which each vertex appears on the outer face, and each edge crosses at most one other edge. The drawing algorithm preserves the embedding of the input graph. This is one of the few algorithms available to construct RAC drawings. [ABSTRACT FROM AUTHOR]

This paper starts the investigation of a constrained version of the point-set embed-dability problem. Let G = (V,E) be a planar graph with n vertices, G′ = (V′,E′) a subgraph of G, and S a set of n distinct points in the plane. We study the problem of computing a point-set embedding of G on S subject to the constraint that G′ is drawn with straight-line edges. Different drawing algorithms are presented that guarantee small curve complexity of the resulting drawing, i.e. a small number of bends per edge. It is proved that: • If G′ is an outerplanar graph and S is any set of points in convex position, a point-set embedding of G on S can be computed such that the edges of E\E′ have at most 4 bends each. • If S is any set of points in general position and G′ is a face of G or if it is a simple path, the curve complexity of the edges of E\E′ is at most 8. • If S is in general position and G′ is a set of k disjoint paths, the curve complexity of the edges of E \ E′ is O(2k). [ABSTRACT FROM AUTHOR]

We study optimization problems for polyhedral terrains in the presence of data imprecision. An imprecise terrain is given by a triangulated point set where the height component of the vertices is specified by an interval of possible values. We restrict ourselves to terrains with a one-dimensional projection, usually referred to as 1.5-dimensional terrains, where an imprecise terrain is given by an x-monotone polyline, and the y-coordinate of each vertex is not fixed but only constrained to a given interval. Motivated mainly by applications in terrain analysis, in this paper we study five different optimization measures related to obtaining smooth terrains, for the 1.5-dimensional case. In particular, we present exact algorithms to minimize and maximize the total turning angle, as well as to minimize the maximum slope change. Furthermore, we also give approximation algorithms to minimize the largest turning angle and to maximize the smallest turning angle. [ABSTRACT FROM AUTHOR]

We implement an algorithm for k-clustering for small k in fixed dimensions and report experimental results here. Although the theoretical bounds on the running time are hopeless for 1 + ∊ approximating k-clusters, we note that for dimensions 2 and 3, k-clustering is practical for small k (k ≤ 4) and simple enough shapes. For the purposes of this paper, k is a small fixed constant. [ABSTRACT FROM AUTHOR]

Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider a generalization of the classical geometric spanner problem (called segment spanner): Given a set S of n disjoint 2-D segments, find a spanning network GS with minimum size so that for any pair of points in S, there exists a path in GS with length no more than t times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, interval cover, and imaginary Steiner points), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set Q of Steiner points in S and then constructs a point spanner for the set of Steiner points. Our algorithm runs in O(|Q| + n2log n) time and Q is a constant approximation (in terms of its size) of the optimal solution when S has a constant relative separation ratio. The approximation ratio depends on the stretch factor t and the relative separation ratio of S. [ABSTRACT FROM AUTHOR]

Consider a geometric network G in the plane. The dilation between any two vertices x and y in G is the ratio of the shortest path distance between x and y in G to the Euclidean distance between them. The maximum dilation over all pairs of vertices in G is called the dilation of G. In this paper, a randomized algorithm is presented which, when given a polygonal cycle C on n vertices in the plane, computes in O(n log3 n) expected time, the edge of C whose removal results in a polygonal path of smallest possible dilation. It is also shown that the edge whose removal gives a polygonal path of largest possible dilation can be computed in O(n log n) time. If C is a convex polygon, the running time for the latter problem becomes O(n). Finally, it is shown that a (1 - ϵ)-approximation to the dilation of every path C \{e}, for all edges e of C, can be computed in O(n log n) total time. [ABSTRACT FROM AUTHOR]

This paper is devoted to the study of vector valued reproducing kernel Hilbert spaces. We focus on two aspects: vector valued feature maps and universal kernels. In particular, we characterize the structure of translation invariant kernels on abelian groups and we relate it to the universality problem. [ABSTRACT FROM AUTHOR]

In this paper, by constructing a more entangled quantum system, we shorten the adiabatic quantum search algorithm to constant time. On the other hand, we show that the speed-up of adiabatic quantum algorithms by selecting particular adiabatic evolution paths or injecting energy into the quantum system can be explained as a form of entanglement enlargement. These findings suggest that entanglement plays a fundamental role for the efficiency of algorithm performance. [ABSTRACT FROM AUTHOR]

We present a novel approach to approximate the smallest disc to enclose an affine IFS attractor at any accuracy. The approach is efficient and characterized by very low memory requirements. It is based on a concept of spanning points we introduce to describe the extent of an IFS attractor. We give the formal definition of these points and show how to construct them efficiently in practice. A proof that the smallest disc to enclose the spanning points includes the smallest enclosing disc of the IFS attractor is given. We also show that the former disc approximates the latter with an error depending on parameters relevant to the construction of the points. The main benefit of using the spanning points is that their number is usually small even for high approximation accuracies. Thus, we can apply with success one of the known, smallest enclosing disc algorithms to the spanning points. The enclosed experimental results obtained for popular IFS fractals confirm the theoretical assertions of the paper, by showing that our method performs well in practice. [ABSTRACT FROM AUTHOR]

Two points a and b are said to be L-visible among a set of polygonal obstacles if the length of the shortest path from a to b avoiding these obstacles is no more than L. For a given convex polygon P with n vertices, Gewali et al.1 addressed the guard placement problem on the boundary of P that covers the maximum area outside to the polygon under L-visibility with P as obstacle. Their proposed algorithm runs in O(n) time if $L\, < \,{{\pi (P)} \over 2}$, where π(P) denotes the perimeter of P. They conjectured that if $L\, \ge \,{{\pi (P)} \over 2}$, then the problem can be solved in subquadratic time. In this paper, we settle the conjecture in the affirmative sense, by proposing an easy to implement linear time algorithm for any arbitrary value of L. [ABSTRACT FROM AUTHOR]

For the purpose of estimating the mixing matrix under the nonstrictly sparse condition, this paper presents the algorithms to approximate the mixing matrix in two different situations in which the source vectors are 1-sparse and (m - 1)-sparse. When the source signals are 1-sparse, we use the generalized spherical coordinate transformation to convert the matrix of observation signals into the new one, which makes the process of estimating column A become the process of finding the center point of these new data. For the situation that source signals are (m - 1)-sparse, we propose a new algorithm for the underdetermined mixtures blind source separation based on hyperplane clustering. The algorithm firstly finds out the linearly independent vectors from the observations, and secondly determines all the normal vectors of hyperplanes by analyzing the number of observations that are in the same hyperplane. Finally, we identify the column vectors of the mixing matrix A by calculating the vectors which are orthogonal to the clustered normal vectors. These two new algorithms for estimating the mixing matrix are more suitable for the general cases as they have lower requirement for the sparsity of the observations. [ABSTRACT FROM AUTHOR]

This paper studies the complexity of determining if a finite algebra generates a variety that satisfies various Maltsev conditions, such as congruence distributivity or modularity. For idempotent algebras we show that there are polynomial time algorithms to test for these conditions but that in general these problems are EXPTIME complete. In addition, we provide sharp bounds in terms of the size of two-generated free algebras on the number of terms needed to witness various Maltsev conditions, such as congruence distributivity. [ABSTRACT FROM AUTHOR]

In this paper, we study the irreducible decompositions of the degeneracy loci of matrices which are defined by rank conditions on upper left submatrices. By introducing the concepts of standard and essential rank functions, we give an explicit classification of these degeneracy loci. Based on standard rank functions, we design an algorithm to write a degeneracy locus as a union of its irreducible components. This gives an answer to a problem raised by Sturmfels. [ABSTRACT FROM AUTHOR]

Stallings showed that every finitely generated subgroup of a free group is canonically represented by a finite minimal immersion of a bouquet of circles. In terms of the theory of automata, this is a minimal finite inverse automaton. This allows for the deep algorithmic theory of finite automata and finite inverse monoids to be used to answer questions about finitely generated subgroups of free groups. In this paper, we attempt to apply the same methods to other classes of groups. A fundamental new problem is that the Stallings folding algorithm must be modified to allow for "sewing" on relations of non-free groups. We look at the class of groups that are amalgams of finite groups. It is known that these groups are locally quasiconvex and thus, all finitely generated subgroups are represented by finite automata. We present an algorithm to compute such a finite automaton and use it to solve various algorithmic problems. [ABSTRACT FROM AUTHOR]

In this paper we produce a finite algebra which generates a variety with a PSPACE-complete membership problem. We produce another finite algebra with a γ function that grows exponentially. The results are obtained via a modification of a construction of the algebra A(T) that was introduced by McKenzie in 1996. [ABSTRACT FROM AUTHOR]

This paper presents a weighted support vector machine (WSVM) to improve the outlier sensitivity problem of standard support vector machine (SVM) for two-class data classification. The basic idea is to assign different weights to different data points such that the WSVM training algorithm learns the decision surface according to the relative importance of data points in the training data set. The weights used in WSVM are generated by a robust fuzzy clustering algorithm, kernel-based possibilistic c-means (KPCM) algorithm, whose partition generates relative high values for important data points but low values for outliers. Experimental results indicate that the proposed method reduces the effect of outliers and yields higher classification rate than standard SVM does when outliers exist in the training data set. [ABSTRACT FROM AUTHOR]

A new multi-class classifier, decision tree SVM (DTSVM) which is a binary decision tree with a very simple structure is presented in this paper. In DTSVM, a problem of multi-class classification is decomposed into a series of ones of binary classification. Here, the binary decision tree is generated by using kernel clustering algorithm, and each non-leaf node represents one binary classification problem. By compared with the other multi-class classification methods based on the binary classification SVMs, the scale and the complexity of DTSVM are less, smaller number of support vectors are needed, and has faster test speed. The final simulation results confirm the feasibility and the validity of DTSVM. [ABSTRACT FROM AUTHOR]

A temporal flexible planning problem that involves contingent and requirement events can be formulated as a simple temporal network with uncertainty (STNU). An STNU is controllable when there is a strategy for executing the requirement events (or actions) in such a way that all the conditions involving contingent events can be satisfied in all situations. The most interesting and useful controllability property is dynamic controllability in which the remaining actions in an STNU can always be scheduled under all possible feasible durations of future contingent events when all the past contingent events are known. In this paper, we propose and study a novel problem of assigning bounds on the duration of each requirement link in order for the resulting STNU to be dynamically controllable and to minimize the total cost over the allowed durations of all requirement links. We first prove the NP hardness of the problem with a linear cost function. We then formulate the dynamic controllability of an STNU as the constraints in a nonlinear optimization problem. Finally, we present methods for reducing the number of constraints in order to make the problem tractable and to demonstrate the computational performance of our methods. [ABSTRACT FROM AUTHOR]

A complex model for evolving the update strategy of a Particle Swarm Optimisation (PSO) algorithm is described in this paper. The model is a hybrid technique that combines a Genetic Algorithm (GA) and a PSO algorithm. Each GA chromosome is an array encoding a meaning for updating the particles of the PSO algorithm. The Evolved PSO algorithm is compared to several human-designed PSO algorithms by using ten artificially constructed functions and one real-world problem. Numerical experiments show that the Evolved PSO algorithm performs similarly and sometimes even better than the Standard approaches for the considered problems. The Evolved PSO is highly scalable (regarding the size of the problem's input), being able to solve problems having different dimensions. [ABSTRACT FROM AUTHOR]

This paper addresses a novel sentence reduction algorithm based on a decision tree model in which semantic information is used to enhance the accuracy of sentence reduction. The proposed algorithm is able to deal with the changeable order problem in sentence reduction. Furthermore, the use of decision list to solve the fragment problem in sentence reduction based decision tree model is also discussed. Our experimental results show an improvement when compared with earlier methods. [ABSTRACT FROM AUTHOR]

Propositional satisfiability (SAT) problem is fundamental to the theory of NP-completeness. Indeed, using the concept of "polynomial-time reducibility" all NP-complete problems can be polynomially reduced to SAT. Thus, any new technique for satisfiability problems will lead to general approaches for thousands of hard combinatorial problems. In this paper, we introduce the incremental propositional satisfiability problem that consists of maintaining the satisfiability of a propositional formula anytime a conjunction of new clauses is added. More precisely, the goal here is to check whether a solution to a SAT problem continues to be a solution anytime a new set of clauses is added and if not, whether the solution can be modified efficiently to satisfy the old formula and the new clauses. We will study the applicability of systematic and approximation methods for solving incremental SAT problems. The systematic method is based on the branch and bound technique while the approximation methods rely on stochastic local search and genetic algorithms. Experimental tests, conducted on randomly generated SAT instances, demonstrate the efficiency in time of the approximation methods over the branch and bound algorithm. However these approximation methods do not always guarantee the completeness of the solution returned. We show that a method we propose that uses non systematic search in a limited form together with branch and bound has the best compromise, in practice, between time and quality of the solution returned (success ratio). [ABSTRACT FROM AUTHOR]

In this paper we prove that two n-gems induce the same manifold if and only if they are linked by a finite sequence of gem moves. A gem move is either a blob move, consisting in the creation or cancellation of an n-dipole, or a clean flip, which is a switch of a pair of edges of the same color that thickens an h-dipole, 1 ≤ h ≤ n - 1, or the inverse operation, which slims an h-dipole, 2 ≤ h ≤ n. Moreover we prove that we can reorder the gem moves, so that all the blob creations precede all clean flips which then precede all the blob cancellations. This reordering is of interest because it is an easy matter to decide whether two gems are linked by a finite sequence of clean flips. As a consequence, if a bound for the number of blob creations is established, then there exists a deterministic finite algorithm to decide whether two gems induce the same manifold or not. [ABSTRACT FROM AUTHOR]

The separation game is different from the connection game, but has some similarities. In the game of Go, it is often useful because it helps to enclose groups and areas. An evaluation function, moves generation functions and a search algorithm for the separation game are described in this paper. [ABSTRACT FROM AUTHOR]

Inference problems are one of the main research topics in the artificial intellect field. So far there have been various inference systems, some of them have been applied in fuzzy control according to their feature. In 1989, the concept of truth-valued flow inference was introduced by Wang1, and its mathematical theory of truth-valued flow inference was set up by Wang2 in 1995. In this paper, aimed at the real meaning of the truth-valued in the truth-valued flow inference, we introduce the concepts of the inner product truth-valued and inner product truth-valued flow inference, and analyze some inference algorithms of fuzzy control at present in detail. We reveal that the fuzzy inference algorithms in fuzzy control at present are all regarded as inner product truth-valued flow inference algorithm. Finally, inner product truth-valued flow inference approach is generalized in the multiple inputs and single output. [ABSTRACT FROM AUTHOR]

In Global Positioning System (GPS), receivers use FFT-based convolvers to acquire the signals. This paper shows a robust substitute algorithm for calculating the convolution that is less sensitive to additive noise. [ABSTRACT FROM AUTHOR]

In this paper, based on a characterization of epimorphisms of R-algebras given by Roby [15], we bring an algorithm testing whether a given finitely generated morphism f : A → B, where A and B are finitely presented affine algebras over the same Nœtherian commutative ring R, is an epimorphism of R-algebras or not. We require two computational conditions on R, which we call a computational ring. [ABSTRACT FROM AUTHOR]

This paper presents a fast algorithm for solving the n-queens problem. The basic idea of this algorithm is to use pre-computed solutions in 75% of the cases, while the remaining cases are solved by calling the Sosic's algorithm. The novelty of this algorithm is in the observation that these pre-computable cases exhibit a modular nature. In addition, the pre-computed solutions run 100 times faster than Sosic's algorithm in most cases. [ABSTRACT FROM AUTHOR]

The Multi-Tier (M-Tier) algorithm proposed in [1], has enabled an enhanced correlation between dynamic resource utilization and QoS guarantees. The algorithm favored the delay sensitive applications. Indirectly, this infers that the assignment of priorities practiced in the algorithm is static. In redesigning the algorithm, priority assignments should be able to be implemented dynamically. Thus, enabling an embedded element to provide implementation mobility. This would depend upon the current status of the classified buffers and the tolerance level of the delay sensitive traffic. Integrating control parameters to enable alternation in scheduling priorities is an option to resolve the element of partiality present in the M-Tier algorithm. Thereafter, the proposed algorithm will be denoted as the M-Tier(T) algorithm [2]. The paper proposes a detailed mathematical model for the analysis of dynamic resource reservation algorithms implemented in IP switches. The semi-markov process (SMP) approach utilized provides an accurate performance prediction and representation of resource reservation mechanisms. The algorithm correlates the average packet delay and packet loss ratio parameters to activate the dynamic resource reservation mechanism in a hierarchical manner. The developed models are validated through discrete-event simulation. The performance of the algorithm is studied in terms of average packet delay and network throughput. [ABSTRACT FROM AUTHOR]

This paper describes an efficient and adaptive method of threshold estimation for removing impulse noise from images, based on Double Density Wavelet Transform (DDWT). The performance of image de-noising algorithms using wavelet transforms can be improved significantly by fixing an optimum threshold value, based on the analysis of the statistical parameters of subband coefficients. In this proposed method, the choice of the threshold estimation is carried out by analyzing the statistical parameters of the wavelet subband coefficients like standard deviation, arithmetic mean and geometrical mean. Here the noisy image is first decomposed into many levels to obtain different frequency bands using DDWT. Then soft thresholding method is used to remove the noisy coefficients, by fixing the optimum threshold value by the proposed method. Experimental results on several test images by using the proposed method show that, the proposed method yields significantly superior image quality and better Peak Signal-to-Noise Ratio (PSNR). Some comparisons with the best available results will be given in order to illustrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The brain has evolved to enable organisms to survive in a complicated and dynamic world. Its operation is based upon a priori models of the environment which are adapted, during learning, in response to new and changing stimuli. The same qualities that make biological learning mechanisms ideal for organisms make their underlying mathematical algorithms ideal for certain technological applications, especially those concerned with understanding the physical processes giving rise to complicated data sets. In this paper, we offer a mathematical model for the underlying mechanisms of biological learning, and we show how this mathematical approach to learning can yield a solution to the problem of imaging time-varying objects from X-ray computed tomographic (CT) data. This problem relates to several practical aspects of CT imaging including the correction of motion artifacts caused by patient movement or breathing. [ABSTRACT FROM AUTHOR]

In Part I, we described an efficient and robust algorithm for computing a common refinement of two surface meshes. In this paper, we present a theoretical verification of the robustness of our algorithm by showing the topological preservation of the intersection principle, which we used to resolve topological inconsistencies caused by numerical errors. To enhance robustness in practice for complex geometries, we further propose techniques to detect and match geometric features, such as ridges, corners, and nonmatching boundaries. We report experimental results using our enhanced overlay algorithm with feature matching for complex geometries from real-world applications. [ABSTRACT FROM AUTHOR]

By analyzing the dynamic behaviors of the transiently chaotic neural network and greedy heuristic for the maximum independent set (MIS) problem, we present an improved transiently chaotic neural network for the MIS problem in this paper. Extensive simulations are performed and the results show that this proposed transiently chaotic neural network can yield better solutions to p-random graphs than other existing algorithms. The efficiency of the new model is also confirmed by the results on the complement graphs of some DIMACS clique instances in the second DIMACS challenge. Moreover, the improved model uses fewer steps to converge to stable state in comparison with the original transiently chaotic neural network. [ABSTRACT FROM AUTHOR]

The first aim of this paper is to give an example of a virtual knot which vanishes all the known invariants and to show that it is a non-classical (in particular, non-trivial) knot. The second is to study some properties of the Z-polynomial of a virtual knot with virtual crossing number one and to show that there are infinitely many virtual knots with virtual crossing number two. [ABSTRACT FROM AUTHOR]

Nakanishi and Shibuya gave a relation between link homotopy and quasi self delta-equivalence. And they also gave a necessary condition for two links to be self delta-equivalent by using the multivariable Alexander polynomial. Link homotopy and quasi self delta-equivalence are also called self C1-equivalence and quasi self C2-equivalence respectively. In this paper, we generalize their results. In Sec. 1, we give a relation between self Ck-equivalence and quasi self Ck+1-equivalence. In Secs. 2 and 3, we give necessary conditions for two links to be self Ck-equivalent by using the multivariable Conway potential function and the Conway polynomial respectively. [ABSTRACT FROM AUTHOR]

Let M be a closed oriented surface of genus g≥1, let Bn(M) be the braid group of M on n strings, and let SBn(M) be the corresponding singular braid monoid. Our purpose in this paper is to prove that the desingularization map η : SBn(M)→ℤ[Bn(M)], introduced in the definition of the Vassiliev invariants (for braids on surfaces), is injective. [ABSTRACT FROM AUTHOR]

It has long been conjectured that the crossing numbers of links are additive under the connected sum of links. This is a difficult problem in knot theory and has been open for more than 100 years. In fact, many questions of much weaker conditions are still open. For instance, it is not known whether Cr(K1#K2)≥Cr(K1) or Cr(K1#K2)≥Cr(K2) holds in general, here K1#K2 is the connected sum of K1 and K2 and Cr(K) stands for the crossing number of the link K. However, for alternating links K1 and K2, Cr(K1#K2)=Cr(K1)+Cr(K2) does hold. On the other hand, if K1 is an alternating link and K2 is any link, then we have Cr(K1#K2)≥Cr(K1). In this paper, we show that there exists a wide class of links over which the crossing number is additive under the connected sum operation. This class is different from the class of all alternating links. It includes all torus knots and many alternating links. Furthermore, if K1 is a connected sum of any given number of links from this class and K2 is a non-trivial knot, we prove that Cr(K1#K2)≥Cr(K1)+3. [ABSTRACT FROM AUTHOR]

In this paper, we consider a set of mobile nodes, each of which moves with constant velocity. We present algorithms to determine which of these mobile nodes can be captured the soonest by a set of one or more pursuers. We use a time parameterized R-tree (TPR-tree) to index these moving points. We then develop algorithms that operate on the TPR-tree to answer three query variations: (1) a single pursuer that is faster than all of the mobile nodes, (2) a single pursuer that is slower than some of the mobile nodes and (3) multiple pursuers. Experimental results show that our algorithms are simpler and faster than other approaches to solve the problem. [ABSTRACT FROM AUTHOR]

Genetic algorithms have been applied to many optimization and search problems and shown to be very efficient. However, the efficiency of genetic algorithms is not guaranteed in those applications where the search space is small, such as the block motion estimation in video coding applications, or equivalently the chromosome length is relatively short, less than 5 for example. Since the characteristics of these small search space applications are far away from the conventional search problems in which the common genetic algorithms worked well. New treatments of genetic algorithms for dealing with the small range search problems are therefore of interest. In this paper, the efficiency (will be defined later) of the genetic operations of common genetic algorithms, such as crossover and mutation, are analyzed for this special situation. As expected, the so-obtained efficiency/performance of the genetic operations is quite different from that of their traditional counterparts. To fill this gap, a lightweight genetic search algorithm is presented to provide an efficient way for generating near optimal solutions for these kinds of applications. The control overheads of the lightweight genetic search algorithm is very low as compared with that of the conventional genetic algorithms. It is shown by simulations that a lot of computations can be saved by applying the newly proposed algorithm while the search results are still well approved. [ABSTRACT FROM AUTHOR]

A fuzzy variable is a function from a possibility space to the set of real numbers, while a bifuzzy variable is a function from a possibility space to the set of fuzzy variables. In this paper, a concept of chance distribution is originally presented for bifuzzy variable, and the linearity of expected value operator of bifuzzy variable is proved. Furthermore, bifuzzy simulations are designed and illustrated by some numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper we define a new class of the quantum integrable systems associated with the quantization of the cotangent bundle T*(GL(N)) to the Lie algebra $\mathfrak{gl}_N$. The construction is based on the Gelfand-Zetlin maximal commuting subalgebra in $U(\mathfrak{gl}_N)$. We discuss the connection with the other known integrable systems based on T*GL(N). The construction of the spectral tower associated with the proposed integrable theory is given. This spectral tower appears as a generalization of the standard spectral curve for an integrable system. [ABSTRACT FROM AUTHOR]

In this paper, we apply OPCL control to discrete system, and based on relative nonlinear measure, give an algorithm for estimating the radius of stable basin. We rigorously prove that this basin is bound to be of existence for nonlinear discrete system, whose goal dynamics is either periodic orbits or fixed point. We also, in particular, investigate the stable basin in a quadratic polynomial map system, and present that the stable basin is irrelevant to the goal orbits with a negative Jacobian gain matrix. Furthermore, we take the well-known Hénon system and Ikeda system as examples to illustrate the implementation of our theory, and give the corresponding simulations to reinforce our method. [ABSTRACT FROM AUTHOR]

An algorithm is proposed in this paper that finds exact exclusive-or sum-of-products of an arbitrary function, provided the number of product terms is less than eight. If the number of product terms in the minimal expression is more than seven, then the algorithm detects it and heuristically returns near-optimal expressions. The algorithm is time and space efficient even for functions with many input variables. [ABSTRACT FROM AUTHOR]