Search

Based on the presentation of the Kauffman bracket skein algebra of the thickened torus given by the third author in previous work [4], Frohman and Gelca established a complete description of the multiplicative operation leading to a famous product-to-sum formula. In this paper, we study the multiplicative structure of the Kauffman bracket skein algebra of the thickened four-holed sphere. We present an algorithm to compute the product of any two elements of the algebra, and give an explicit formula for some families of curves. We surmise that the algorithm has quasi-polynomial growth with respect to the number of crossings of a pair of curves. Further, we conjecture the existence of a positive basis for the algebra. [ABSTRACT FROM AUTHOR]

This paper proposes the matrix representation of formal polynomials over max-plus algebra and obtains the maximum and minimum canonical forms of a polynomial function by standardizing this representation into a canonical form. A necessary and sufficient condition for two formal polynomials corresponding to the same polynomial function is derived. Such a matrix method is constructive and intuitive, and leads to a polynomial algorithm for factorization of polynomial functions. Some illustrative examples are presented to demonstrate the results. [ABSTRACT FROM AUTHOR]

The computation of a maximal order of an order in a semisimple algebra over a global field is a classical well-studied problem in algorithmic number theory. In this paper, we consider the related problems of computing all minimal overorders as well as all overorders of a given order. We use techniques from algorithmic representation theory and the theory of minimal integral ring extensions to obtain efficient and practical algorithms, whose implementation is publicly available. [ABSTRACT FROM AUTHOR]

In the graph of a complex network, the algebraic connectivity is the second smallest eigenvalue of a Laplacian matrix. In this paper, we present a cut algorithm based on edge centrality by minimizing the algebraic connectivity of graph. The edge centrality cut algorithm (ECCA) cuts edges at a time in order to reduce temporal complexity, the algebraic connectivity of which experiences the fastest decline. To prevent nodes from overcutting, each edge sets the weight. We use the advanced ECCA (AECCA) to detect overlapping communities by calculating the correlation coefficients of the nodes. This paper also proposes upper, lower and weaker lower bounds of algebraic connectivity. We demonstrate that our algorithms are effective and accurate at discovering community structure in both artificial and real-world network data and that the algebraic connectivity of the cut algorithm lies between the upper and lower bounds. Our algorithms offer new insights into community detection by calculating the edge centrality. [ABSTRACT FROM AUTHOR]

Coarse-graining of complex networks is one of the important algorithms to study large-scale networks, which is committed to reducing the size of networks while preserving some topological information or dynamic properties of the original networks. Spectral coarse-graining (SCG) is one of the typical coarse-graining algorithms, which can keep the synchronization ability of the original network well. However, the calculation of SCG is large, which limits its real-world applications. And it is difficult to accurately control the scale of the coarse-grained network. In this paper, a new SCG algorithm based on K-means clustering (KCSCG) is proposed, which cannot only reduce the amount of calculation, but also accurately control the size of coarse-grained network. At the same time, KCSCG algorithm has better effect in keeping the network synchronization ability than SCG algorithm. A large number of numerical simulations and Kuramoto-model example on several typical networks verify the feasibility and effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we characterize the classification of unimodal maps from the plane to the plane with respect to 𝒜 -equivalence given by Rieger in terms of invariants. We recall the classification over an algebraically closed field of characteristic 0. On the basis of this characterization, we present an algorithm to compute the type of the unimodal maps from the plane to the plane without computing the normal form and also give its implementation in the computer algebra system Singular. [ABSTRACT FROM AUTHOR]

The Kautz digraphs K(d, ℓ) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related to these, the cyclic Kautz digraphs CK(d, ℓ) were recently introduced by Böhmová, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to the cyclic Kautz digraphs by introducing the family of the subKautz digraphs sK(d, ℓ), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d, ℓ) and CK(d, ℓ). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d, ℓ) and CK(d, ℓ) are maximally vertex-connected and super-edge-connected. Whereas K(d, ℓ) are optimal with respect to the diameter, we show that sK(d, ℓ) and CK(d, ℓ) are optimal with respect to the mean distance, whose exact values are given for both families when ℓ = 3. Finally, we provide a lower bound on the girth of CK(d, ℓ) and sK(d, ℓ). [ABSTRACT FROM AUTHOR]

In this research, a framework is proposed for answering the question: whether a dominant sequence exists for the multiple self-contained input streams destined for a computation provider running the requested applications concurrently. The framework is extended to find an optimal semidominant sequence for multiple input streams. This paper also shows that an existent universal dominant sequence can be formed by permuting a set of dominant input streams. In this paper, the neighbor-connected graph is first proposed to model the sequence problem of multiple input streams. Then, an algorithm with time complexity O(nLn) is proposed to determine the existence of a dominant data-receiving sequence, where L is the maximal length of the input streams plus one and n is the number of input streams. Examples of applying the framework to solve the sequence problems for several computation-intensive applications are also given. Furthermore, the framework is extended to find an optimal semidominant sequence using an algorithm with time complexity O(nLnlogδ*), where δ* is the maximal degree that the sequence diverges from all the optimal subsequences. Finally, the property of a universal dominant sequence is studied and the performance of the sequence is compared with those of other sequences. [ABSTRACT FROM AUTHOR]

This paper presents a wavelet-based computationally efficient implementation of the Linear Minimum Mean Square Error (LMMSE) algorithm in image super-resolution. The image super-resolution reconstruction problem is well-known to be an ill-posed inverse problem of large dimensions. The LMMSE estimator to be implemented in the image super-resolution reconstruction problem requires an inversion of a very large dimension matrix, which is practically impossible. Our suggested implementation is based on breaking the problem into four consecutive steps, a registration step, a multi-channel LMMSE restoration step, a wavelet-based image fusion step and an LMMSE image interpolation step. The objective of the wavelet fusion step is to integrate the data obtained from each observation into a single image, which is then interpolated to give a high-resolution image. The paper explains the implementation of each step. The proposed implementation has succeeded in obtaining a high-resolution image from multiple degraded observations with a high PSNR. The computation time of the suggested implementation is small when compared to traditional iterative image super-resolution algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the little q-Schur algebra s(2,r) of type A1. The main purpose of this paper is to construct a monomial base of s(2,r). [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 generalized approach to 2D CA PRNGs — the 2D lattice CA PRNG — by introducing vertical connections to arrays of 1D CA. The structure of a 2D lattice CA PRNG lies in between that of 1D CA and 2D CA grid PRNGs. With the generalized approach, 2D lattice CA PRNG offers more 2D CA PRNG variations. It is found that they can do better than the conventional 2D CA grid PRNGs. In this paper, the structure and properties of 2D lattice CA are explored by varying the number and location of vertical connections, and by searching for different 2D array settings that can give good randomness based on Diehard test. To get the most out of 2D lattice CA PRNGs, genetic algorithm is employed in searching for good neighborhood characteristics. By adopting an evolutionary approach, the randomness quality of 2D lattice CA PRNGs is optimized. In this paper, a new metric, #rn is introduced as a way of finding a 2D lattice CA PRNG with the least number of cells required to pass Diehard test. Following the introduction of the new metric #rn, a cropping technique is presented to further boost the CA PRNG performance. The cost and efficiency of 2D lattice CA PRNG is compared with past works on CA PRNGs. [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]

Partitioned Optical Passive Stars (POPS) network has been presented recently as a desirable model of parallel computation. Several papers have been published that address fundamental problems on this architecture. The algorithms presented in this paper are valid for POPS(d,g) where d>g and use randomization. We present an algorithm that solves the problem of sparse enumeration sorting of d∊ keys in $\widetilde O(\frac{d}{g}\rceil+\log g)$ time and hence performs better than previous algorithms. We also present algorithms that allow us to do stable sorting of integers in the range [1,log n] and $[1, \frac{d}{g}]$ in $\widetilde O(\lceil \frac{d}{g}\rceil+\log n)$ time. When g=n∊, for any constant 0<∊<½ this allows us to do sorting of integers in the range [1,n] in $\widetilde O(\frac{1}{1-2\epsilon}(\lceil\frac{d}{g}\rceil+\log g))$ time. We finally use these algorithms to solve the problem of multiple binary search in the case where we have d∊ keys in $\widetilde O(\frac{d}{g}+\log g)$ time and in the case where we have integer keys in the range [1,n] in $\widetilde O(\frac{1}{1- 2\epsilon}(\lceil\frac{d}{g}\rceil+\log g))$ time, when g=n∊, for some constant 0<∊<½. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for solving a class of large scale nonlinear programming which is originally derived from the multi-stage stochastic convex nonlinear programming. With the Lagrangian-dual method and the Moreau-Yosida regularization, the primal problem is transformed into a smooth convex problem. By introducing a self-concordant barrier function, an approximate generalized Newton method is designed in this paper. The algorithm is shown to be of superlinear convergence. At last, some preliminary numerical results are provided. [ABSTRACT FROM AUTHOR]

The box counting algorithm is a well-known method for the computation of the fractal dimension of an image. It is often implemented using a recursive subdivision of the image into a set of regular tiles or boxes. Parallel implementations often try to map the boxes to different compute units, and combine the results to get the total number of boxes intersecting a shape. This paper presents a novel and highly efficient method using Open Computing Language (OpenCL) kernels to perform the computation on a per-pixel basis. The mapping and reduction stages are performed in a single pass, and therefore require the enqueuing of only a single kernel. Each instance of the kernel updates the information pertaining to all the boxes containing the pixel, and simultaneously increments the box counters at multiple levels, thereby eliminating the need for another pass to perform the summation. The complete implementation and coding details of the proposed method are outlined. The performance of the method on different processors are analyzed with respect to varying image sizes. [ABSTRACT FROM AUTHOR]

In this paper, we present an algorithm to automatically detect meaningful modes in a histogram. The proposed method is based on the behavior of local minima in a scale-space representation. We show that the detection of such meaningful modes is equivalent in a two classes clustering problem on the length of minima scale-space curves. The algorithm is easy to implement, fast and does not require any parameter. We present several results on histogram and spectrum segmentation, grayscale image segmentation and color image reduction. [ABSTRACT FROM AUTHOR]

Given any fixed integer q ≥ 2, a q-monomial is of the format such that 1 ≤ sj ≤ q - 1, 1 ≤ j ≤ t. q-monomials are natural generalizations of multilinear monomials. Recent research on testing multilinear monomials and q-monomials for prime q in multivariate polynomials relies on the property that Zq is a field when q ≥ 2 is prime. When q > 2 is not prime, it remains open whether the problem of testing q-monomials can be solved in some compatible complexity. In this paper, we present a randomized O*(7.15k) algorithm for testing q-monomials of degree k that are found in a multivariate polynomial that is represented by a tree-like circuit with a polynomial size, thus giving a positive, affirming answer to the above question. Our algorithm works regardless of the primality of q and improves upon the time complexity of the previously known algorithm for testing q-monomials for prime q > 7. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to improve the bound of complexity of the well-known algorithms on polynomial ideals having complexities polynomial in dn, where d is the maximal degree of input polynomials and n is the number of variables. Instead of this bound, we present the more accurate bound max{S, Dn} where S is the size of the input polynomials in dense representation, and D is the arithmetic mean value of the degrees of input polynomials. [ABSTRACT FROM AUTHOR]

In this paper we develop an axiomatic setup for algorithmic homological algebra of Abelian categories. This is done by exhibiting all existential quantifiers entering the definition of an Abelian category, which for the sake of computability need to be turned into constructive ones. We do this explicitly for the often-studied example Abelian category of finitely presented modules over a so-called computable ring R, i.e. a ring with an explicit algorithm to solve one-sided (in)homogeneous linear systems over R. For a finitely generated maximal ideal 픪 in a commutative ring R, we show how solving (in)homogeneous linear systems over R픪 can be reduced to solving associated systems over R. Hence, the computability of R implies that of R픪. As a corollary, we obtain the computability of the category of finitely presented R픪-modules as an Abelian category, without the need of a Mora-like algorithm. The reduction also yields, as a byproduct, a complexity estimation for the ideal membership problem over local polynomial rings. Finally, in the case of localized polynomial rings, we demonstrate the computational advantage of our homologically motivated alternative approach in comparison to an existing implementation of Mora's algorithm. [ABSTRACT FROM AUTHOR]

In view of the support vectors of ε-SVR that are not distributed in the ε belt and only located on the outskirts of the ε belt, a novel algorithm to construct ε-SVR of a large-scale training sample set is proposed in this paper. It computes firstly the ε-SVR hyper-plane of a small training sample set and the distances d of all samples to the hyper-plane, then deletes the samples not in field ε ≤ d ≤ dmax and searches SVs gradually in the scope ε ≤ d ≤ dmax, and trains step-by-step the final ε-SVR. Finally, it analyzes the time complexity of the algorithm, and verifies its convergence in the theory and tests its efficiency by the simulation. [ABSTRACT FROM AUTHOR]

While Maximum-Likelihood (ML) is the optimum decoding scheme for most communication scenarios, practical implementation difficulties limit its use, especially for Multiple Input Multiple Output (MIMO) systems with a large number of transmit or receive antennas. Tree-searching type decoder structures such as Sphere decoder and K-best decoder present an interesting trade-off between complexity and performance. Many algorithmic developments and VLSI implementations have been reported in literature with widely varying performance to area and power metrics. In this semi-tutorial paper we present a holistic view of different Sphere decoding techniques and K-best decoding techniques, identifying the key algorithmic and implementation trade-offs. We establish a consistent benchmark framework to investigate and compare the delay cost, power cost, and power-delay-product cost incurred by each method. Finally, using the framework, we propose and analyze a novel architecture and compare that to other published approaches. Our goal is to explicitly elucidate the overall advantages and disadvantages of each proposed algorithms in one coherent framework. [ABSTRACT FROM AUTHOR]

Prevalent discretization methods based on Delaunay triangulations and advancing fronts, which sample and mesh simultaneously, can guarantee well shaped triangles but at a fairly high computational cost. In this paper we present a novel and flexible two-part sampling and meshing algorithm, which produces topologically correct meshes on arbitrary boundary representations whose faces are represented parametrically, without requiring an initial coarse mesh. Our method is based on a hybrid spatial partitioning scheme driven by user-designed subdivision rules that combines the power of quadtree decomposition with the flexibility of the binary decompositions to produce meshes that favor prescribed geometric properties. Importantly, the algorithm offers a performance increase of approximately two orders of magnitude over Delaunay based methods and at least one order of magnitude over advancing front methods. At the same time, our algorithm is practically as fast as the computationally optimal algorithm based on a pure quadtree decomposition, but with a markedly better distribution in the regions with parametric distortion. The hierarchical nature of our surface decomposition is well suited to interactive applications and multithreaded implementation. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a generalized version of the Watchman Route Problem (WRP) where the objective is to plan a continuous closed route in a polygon (possibly with holes) and a set of discrete viewpoints on the planned route such that every point on the polygon boundary is visible from at least one viewpoint. Each planned viewpoint has some associated cost. The total cost to minimize is a weighted sum of the view cost, proportional to the number of viewpoints, and the travel cost, the total length of the route. We call this problem the Generalized Watchman Route Problem or the GWRP. We tackle a restricted nontrivial (it remains NP-hard and log-inapproximable) version of GWRP where each polygon edge is entirely visible from at least one planned viewpoint. We call it Whole Edge Covering GWRP. The algorithm we propose first constructs a graph that connects O(n12) number of sample viewpoints in the polygon, where n is the number of polygon vertices; and then solves the corresponding View Planning Problem with Combined View and Traveling Cost, using an LP-relaxation based algorithm we introduced in [27, 29]. We show that our algorithm has an approximation ratio in the order of either the view frequency, defined as the maximum number of sample viewpoints that cover a polygon edge, or a polynomial of log n, whichever is smaller. [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]

In this paper, we propose a new hybrid Bivariate Complex Fourier Wavelet Regularized Deconvolution (Bi-ComForWaRD) that is an extension to the ComForWaRD algorithm, for medical imaging. This new algorithm is a two-step process, a global blur compensation using generalized Wiener filter and followed by a denoising algorithm using local adaptive Bivariate shrinkage function. It is a low-complexity denoising algorithm using the joint statistics of the wavelet coefficients and considers the statistical dependencies between the coefficients. And also, the performance of this system will be demonstrated on both the orthogonal wavelet transform and the dual-tree complex wavelet transform (DT-CWT) and some comparisons with the best available wavelet-based image denoising results will be given in order to illustrate the effectiveness of the system. [ABSTRACT FROM AUTHOR]

An algebra ${\cal R}$ is called an extension of the algebra M by B if M2 = 0, M is an ideal of ${\cal R}$ and ${\cal R}/M\cong B$ as algebras. In this paper, by using Gröbner–Shirshov bases, we characterize completely the extensions of M by B. An algorithm to find the conditions of an algebra A to be an extension of M by B is obtained. [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, an algorithm for constructing a class of orthogonal two-direction refinable functions and the corresponding orthogonal two-direction wavelets is obtained. In addition, the relation of both two-direction refinable functions and multiwavelets is discussed. We discover that Chui–Lian's orthogonal symmetric/antisymmetric multiscaling functions and the corresponding multiwavelets can be recovered by using an orthogonal two-direction refinable function and the corresponding two-direction wavelets, respectively. Finally, some construction examples are given. [ABSTRACT FROM AUTHOR]

In this paper, a Gröbner–Shirshov basis for the Chinese monoid is obtained and an algorithm for the normal form of the Chinese monoid is given. [ABSTRACT FROM AUTHOR]

In this paper, we numerically investigate the structural characteristics that affect the synchronizability of coupled identical oscillators on scale-free networks. By using the edge-exchange method, we can change the network structure with degree sequence fixed. An optimal algorithm, namely Tabu Search, is applied, respectively, to enhance and weaken the synchronizability. The numerical results indicate that the synchronizability is most sensitive to the maximal betweenness. By tracking the optimization process, most previous works suggest that the synchonizability can be enhanced by reducing assortative coefficient and clustering coefficient; however, interestingly, our numerical simulations show that the depression of synchronizability also corresponds to the reduction process of those two coefficients. [ABSTRACT FROM AUTHOR]

In this paper, a high-order Recursive Quadratic (RQ) algorithm is introduced, and the features of this algorithm are thoroughly studied and illustrated. In addition, a robust RQ algorithm is also developed in the presence of general bounded noisy data to enhance model robustness. A numerical example is included to demonstrate the efficiency of RQ algorithms by comparing the results with both the projection algorithm and the conventional recursive least squares algorithm. Also some simulations are carried out to illustrate the effectiveness of the RQ and robust RQ algorithms. [ABSTRACT FROM AUTHOR]

In this article we give a self-contained existence and uniqueness proof for the Tits simple group T. Parrott gave the first uniqueness proof. Whereas Tits' and Parrott's results employ the theory of finite groups of Lie type, our existence and uniqueness proof follows from the general algorithms and uniqueness criteria for abstract finite simple groups described in the first author's book [11]. All we need from the previous papers is the fact that the centralizer H of the Tits group T is an extension of a 2-group J with order 29 and nilpotency class 3 by a Frobenius group F of order 20 such that the center Z(H) has order 2 and any Sylow 5-subgroup Q of H has a centralizer CJ(Q) ≤ Z(H). [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]

In this paper we consider the problem of testing an arbitrary digraph G = (V,E) for upward planarity. In particular we describe two fixed-parameter tractable algorithms for testing the upward planarity of G. The first algorithm that we present can test the upward planarity of G in O(2t · t! · |V|2)-time where t is the number of triconnected components of G. The second algorithm that we present uses a standard technique known as kernelisation and can test the upward planarity of G in O(|V|2 + k4 · (2k)!)-time, where k = |E| - |V|. [ABSTRACT FROM AUTHOR]

A finite p-group G is called metacyclic if it has a cyclic normal subgroup A such that G/A is cyclic. In 1973, King classified metacyclic p-groups; in 1987, Newman and the first author developed a new approach to metacyclic p-groups suggested by the p-group generation algorithm, they found new presentations for these groups. However, their results were only announced in the case of p odd, and no proof was given. The purpose of this paper is to give a new proof of their results in the case of p=2, which is independent of the p-group generation algorithm. [ABSTRACT FROM AUTHOR]

In this paper we investigate the problem of designing load balancing protocols in distributed systems involving self-interested participants. These participants have their own requirements and objectives and no a-priori motivation for cooperation. Their selfish behavior may lead to poor performance and inefficiency. To address this problem we design a load balancing mechanism with verification that provides incentives to participants to report their true parameters and follow the given algorithm. We prove that our load balancing mechanism is truthful (i.e., agents will be better off by reporting their true parameters) and satisfies the voluntary participation condition (i.e., truthful agents never incur a loss). We present a simulation study to show the performance of our load balancing mechanism. [ABSTRACT FROM AUTHOR]

In this paper we present new results on sequential and parallel construction of optimal and almost-optimal length-restricted prefix-free codes. We show that length-restricted prefix-free codes with error 1/nk for any k > 0 can be constructed in O(n log n) time, or in O(log n) time with n CREW processors. A length-restricted code with error 1/nk for any k ≤ L/ logΦ n, where $\Phi = (1 + \sqrt{5})/2$, can be constructed in O(log n) time with n/ log n CREW processors. We also describe an algorithm for the construction of optimal length-restricted codes with maximum codeword length L that works in O(L) time with n CREW processors. [ABSTRACT FROM AUTHOR]

In order to improve the performance of mass segmentation on mammograms, an intelligent algorithm is proposed in this paper. It establishes two mass models to characterize the various masses, and the ones in the denser tissue are represented with Model I, while the ones in the fatty tissue are represented with Model II. Then, it uses iterative thresholding to extract the suspicious area, as well as the rough regions of those masses matching Model II, and applies a DWT-based technique to locate those masses matching Model I, which are hidden in the high gray-level intensity and contrast area. A region growing process restricted by Canny edge detection is subsequently used to segment the rough regions of those masses matching Model I, and finally snakes are carried out to find all the mass regions roughly extracted above. Thirty patient cases with 60 mammograms and 107 masses were used for evaluation, and the experimental result has demonstrated the algorithm's better performance over the conventional methods. [ABSTRACT FROM AUTHOR]

Typical floorplanning problem concerns a series of objectives, such as area, wirelength and routability, etc., without any specific constraint in a free-outline style. Entering SOC era; however, modern floorplanning takes more care of providing extra options, such as boundary constraint for I/O connections and fixed-outline constraint for hierarchical designs. It has been empirically shown that one of the modern constraints extremely restricts the solution space; that is, a large number of randomly generated floorplans might be infeasible. This paper tackles modern floorplanning with both boundary and fixed-outline constraints. A novel genetic clustering algorithm was proposed to guarantee to produce slicing floorplans with satisfying boundary constraint. By analyzing the properties of the slicing floorplan, the algorithm is effective to cluster the boundary-constrained modules into four constrained sub-floorplans. Afterward, the four sub-floorplans were combined to satisfy the boundary constraint. We then extend the algorithm with minor modification to enable the slicing floorplans with boundary constraint to be gradually fit into the desirable fixed outline. The methods were verified by using the MCNC and GSRC benchmarks, and the empirical results show that our methods can obtain promising solutions using short time. [ABSTRACT FROM AUTHOR]

In this paper, a new three-operand modulo (2p ± 1) addition is implemented by performing a carry-save addition and a two-operand modular addition based on the p-digit radix-two signed-digit (SD) number system. Thus, the delay time of the three-operand modular adder is independent of the word length of the operands. A modulo (2p ± 1) multiplier is constructed as a ternary tree of the three-operand modular SD adders, and the modular multiplication time is proportional to log3 p. When a serial modular multiplier is constructed using the three-operand modular SD adder, two modular partial products can be added to the sum at the same time. Two kinds of Booth recoding methods are also proposed to reduce the partial products from p to p/2. Therefore, the performance of a parallel modular multiplier can be modified by reducing half of the modular SD adders in the adder tree. For a serial modular multiplication, two partial products are generated from two Booth recoders and added to the sum by using one three-operand modular SD adder, so that the speed of the modular multiplication is three times as fast as the speed without using the three-operand modular SD adder and the Booth recoding method. A very large-scale integration (VLSI) implementation method by VHDL is also discussed. The design and simulation results show that high-speed modular multipliers can be obtained by the algorithms presented. [ABSTRACT FROM AUTHOR]

The conventional trend in algorithm implementation has been the reliance on advancements in process technology in order to satisfy the ever-increasing demand for high-speed and low power processors, and computational systems. As current device technology approaches sub-100 nm minimum device size, not only does the device geometry decrease, but switching times and operating voltages also scale down. These gains come at the expense of increased layout complexity, and a greater susceptibility to parasitic effects in the interconnections. In this paper we briefly overview the challenges that digital arithmetic designers will have to face in the imminent future, and we provide suggestions on algorithmic measures which may be taken in order to overcome some of these challenges. To illustrate our point, we will present an analysis of a digital multiplication algorithm, which is predicted to outperform currently preferred architectures for future technologies. We then apply the algorithm to form a multiplier architecture that alleviates many of the problems associated with interconnect scaling; in addition, our new architecture allows for simple variable precision reconfiguration. [ABSTRACT FROM AUTHOR]

Pevzner and Sze19 have introduced the Planted (l,d)-Motif Problem to find similar patterns (motifs) in sequences which represent the promoter regions of co-regulated genes, where l is the length of the motif and d is the maximum Hamming distance around the similar patterns. Many algorithms have been developed to solve this motif problem. However, these algorithms either have long running times or do not guarantee the motif can be found. In this paper, we introduce new algorithms to solve this motif problem. Our algorithms can find motifs in reasonable time for not only the challenging (9, 2), (11, 3), (15, 5)-motif problems but for even longer motifs, say (20, 7), (30, 11) and (40, 15), which have never been seriously attempted by other researchers because of the large time and space required. Besides, our algorithms can be extended to find more complicated motifs structure called cis-regulatory modules (CRM). [ABSTRACT FROM AUTHOR]

This paper proposes a practical framework for quantum programming. In our framework, the parts of a program to be performed on a quantum computer are almost automatically determined, and the other parts are performed on a classical computer. We only consider Grover Search to be performed on a quantum computer in the framework because the other quantum algorithms known so far cannot be applied to general cases. By considering only Grover Search, we have several advantages that show our framework is really practical. [ABSTRACT FROM AUTHOR]

The joint measurement approach has been shown to detect more information in quantum system. In this paper, we propose a quantum identification algorithm based on the joint quantum measurement. Through this, we can collectively compare an unknown quantum composite system with those in the database. In addition, this study will show that the proposed quantum algorithm can speed up the identification process quadratically. [ABSTRACT FROM AUTHOR]

For an endomorphism σ of a ring R, Krempa called σ a rigid endomorphism if aσ(a)=0 implies a=0 for a∈R. A ring R is called rigid if there exists a rigid endomorphism of R. In this paper, we extend the σ-rigid property of a ring R to an ideal of R. For a σ-ideal I of a ring R, we call I a σ-rigid ideal if aσ(a)∈I implies a∈I for a∈R. We characterize σ-rigid ideals and study related properties. The connections of the prime radical and the upper nil radical of R with the prime radical and the upper nil radical of the Ore extension R[x;σ,δ], respectively, are also investigated. [ABSTRACT FROM AUTHOR]

The excessive computational resources required by the Nearest Neighbor rule are a major concern for a number of specialists and practitioners in the Pattern Recognition community. Many proposals for decreasing this computational burden, through reduction of the training sample size, have been published. This paper introduces an algorithm to reduce the training sample size while preserving the original decision boundaries as much as possible. Consequently, the algorithm tends to obtain classification accuracy close to that of the whole training sample. Several experimental results demonstrate the effectiveness of this method when compared to other reduction algorithms based on similar ideas. [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]

We consider the following online scheduling problem. We are given a set of jobs, each having an integral release time and deadline, unit processing length, and a nonnegative real weight. In each time unit one job is to be scheduled, and the objective is to maximize the total value (weight) obtained by scheduling the jobs. This problem arises in the scheduling of packets in network switches supporting quality-of-service (QoS). Previous algorithms for this problem are 2-competitive. in this paper we propose a new algorithm that achieves an improved competitive ratio when the importance ratio is bounded. Specifically, for job weights within the range [1..B], our algorithm is 2 - 1/([lg B] + 2)-competitive, and the bound is tight. [ABSTRACT FROM AUTHOR]