Search

In this paper, we consider the discrete unit square cover (DUSC) problem as follows: given a set 𝒫 of n points and a set 𝒮 of m axis-aligned unit squares in ℝ 2 , the objective is (i) to check whether the union of the squares in 𝒮 covers all the points in 𝒫 , and (ii) if the answer is yes, then select a minimum cardinality subset 𝒮 ∗ ⊆ 𝒮 such that each point in 𝒫 is covered by at least one square in 𝒮 ∗ . For the DUSC problem: (i) we propose a (2 + 4 k − 2) -approximation algorithm, where k (> 2) is an integer parameter that defines a trade-off between the running time and the approximation factor of the algorithm. The running time of our proposed algorithm is O (k m k n + n log n). Our solution of the DUSC problem is based on a simple (1 + 2 k − 2) -approximation algorithm for the subproblem strip square cover (SSC) problem, where all the points in 𝒫 are lying within a horizontal strip of unit height. (ii) we also propose a 2-approximation algorithm, which runs in O (m 4 n) time. The 2-approximation algorithm is based on an algorithm for the subproblem SSC problem. The algorithm for the subproblem is developed using plane sweep and graph search traversal techniques. We also extend this algorithm to get 2-approximation result for the weighted DUSC problem where the squares are assigned weights, and the aim is to choose a subset 𝒮 ∗ ⊆ 𝒮 such that each point in 𝒫 is covered by at least one square in 𝒮 ∗ and the sum of the weights of squares in 𝒮 ∗ is minimized. [ABSTRACT FROM AUTHOR]

Music plays a prominent role in society and companies have even started studying its aspects for commercial purposes. It is only natural to ask what characteristics make certain songs appealing. While much research has been conducted on the mathematical principles of sound, there has been less focus on analyzing the structure of popular songs from a mathematical perspective. One mathematical tool that researchers have used to study musical structure is seriation, ordering. This paper applies several types of seriation algorithms to conduct a mathematical analysis of the structural qualities of several musical pieces. This paper focuses on 10 popular artists and their musical influences. The artists chosen for this research are linked because of the influences they cite, musical genre, and the popularity of their music. Results show that an artist's songs have a higher quantitatively measured connection with the artists they cite as influences rather than the artists who they never mention as musical influences. [ABSTRACT FROM AUTHOR]

Differential privacy becomes a standard for evaluating the privacy protection performance for an algorithm these years. However, the definition of differential privacy seems not so easy to understand as the classical k-anonymity and etc. In this paper, we propose a new measure which is more comprehensible. Some properties of such measure are investigated and the relationship between our new definition and differential privacy is studied. [ABSTRACT FROM AUTHOR]

In particular, imprecise observations or possible perturbations mean that data in a network flows may well be better represented by intervals or fuzzy numbers than crisp quantities. In this paper we first consider the minimum cost flow problem with compact interval-valued lower and upper bounds, flows, and costs. We present a new method that shows this problem is solved using two minimum cost flow problems with crisp data. Then this result is extended to networks with fuzzy lower and upper bounds, flows, and costs. One of the best algorithms to solve the minimum cost flow problem with crisp data is the cost scaling algorithm of Goldberg and Tarjan.17 In this paper, the cost scaling algorithm is modified for fuzzy lower and upper bounds, flows and costs. The running time of the modified algorithm is equal to the running time of the cost scaling algorithm with crisp data. [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 defines the 3D reconstruction problem as the process of reconstructing a 3D scene from numerous 2D visual images of that scene. It is well known that this problem is ill-posed, and numerous constraints and assumptions are used in 3D reconstruction algorithms in order to reduce the solution space. Unfortunately, most constraints only work in a certain range of situations and often constraints are built into the most fundamental methods (e.g. Area Based Matching assumes that all the pixels in the window belong to the same object). This paper presents a novel formulation of the 3D reconstruction problem, using a voxel framework and first order logic equations, which does not contain any additional constraints or assumptions. Solving this formulation for a set of input images gives all the possible solutions for that set, rather than picking a solution that is deemed most likely. Using this formulation, this paper studies the problem of uniqueness in 3D reconstruction and how the solution space changes for different configurations of input images. It is found that it is not possible to guarantee a unique solution, no matter how many images are taken of the scene, their orientation or even how much color variation is in the scene itself. Results of using the formulation to reconstruct a few small voxel spaces are also presented. They show that the number of solutions is extremely large for even very small voxel spaces (5 × 5 voxel space gives 10 to 107 solutions). This shows the need for constraints to reduce the solution space to a reasonable size. Finally, it is noted that because of the discrete nature of the formulation, the solution space size can be easily calculated, making the formulation a useful tool to numerically evaluate the usefulness of any constraints that are added. [ABSTRACT FROM AUTHOR]

This paper introduces a multiscale analysis based on optimal piecewise linear approximations of time series. An optimality criterion is formulated, and on its base, a computationally effective algorithm is constructed for decomposition of a time series into a hierarchy of trends (local linear approximations) at different scales. The top of the hierarchy is the global linear approximation over the whole observational interval, the bottom is the original time series. Each internal level of the hierarchy corresponds to a piecewise linear approximation of analyzed series. Possible applications of the introduced Multiscale Trend Analysis (MTA) go far beyond the linear interpolation problem: This paper develops and illustrates methods of self-affine, hierarchical, and correlation analyses of time series. [ABSTRACT FROM AUTHOR]

In this paper we formalize a combinatorial object for describing link diagrams called a Planar Diagram Code (PD-Code). PD-codes are used by the KnotTheory Mathematica package developed by Bar-Natan et al. We present the set of PD-codes as a standalone object and discuss its relationship with link diagrams. We give an explicit algorithm for reconstructing a knot diagram on a surface from a PD-code. We also discuss the intrinsic symmetries of PD-codes (i.e. invertibility and chirality). The moves analogous to the Reidemeister moves are also explored, and we show that the given set of PD-codes modulo these combinatorial Reidemeister moves is equivalent to classical link theory. [ABSTRACT FROM AUTHOR]

If a rectangular diagram represents the trivial knot, then it can be deformed into the trivial rectangular diagram with only four edges by a finite sequence of merge operations and exchange operations, without increasing the number of edges, which was shown by Dynnikov in [Arc-presentations of links: Monotone simplification, Fund. Math. 190 (2006) 29-76; Recognition algorithms in knot theory, Uspekhi Mat. Nauk 58 (2003) 45-92. Translation in Russian Math. Surveys 58 (2003) 1093-1139]. Using this, Henrich and Kauffman gave in [Unknotting unknots, preprint (2011), arXiv:1006.4176v4 [math.GT]] an upper bound for the number of Reidemeister moves needed for unknotting a knot diagram of the trivial knot. However, exchange or merge moves on the top and bottom pairs of edges of rectangular diagrams are not considered in [Unknotting unknots, preprint (2011), arXiv:1006.4176v4 [math.GT]]. In this paper, we show that there is a rectangular diagram of the trivial knot which needs such an exchange move for being unknotted, and study upper bound of the number of Reidemeister moves needed for realizing such an exchange or merge move. [ABSTRACT FROM AUTHOR]

This paper considers *-graphs in which all vertices have degree 4 or 6, and studies the question of calculating the genus of orientable 2-surfaces into which such graphs may be embedded. A *-graph is a graph endowed with a formal adjacency structure on the half-edges around each vertex, and an embedding of a *-graph is an embedding under which the formal adjacency relation on half-edges corresponds to the adjacency relation induced by the embedding. *-graphs are a natural generalization of four-valent framed graphs, which are four-valent graphs with an opposite half-edge structure. In [Embeddings of four-valent framed graphs into 2-surfaces, Dokl. Akad. Nauk 424(3) (2009) 308-310], the question of whether a four-valent framed graph admits a ℤ2-homologically trivial embedding into a given surface was shown to be equivalent to a problem on matrices. We show that a similar result holds for *-graphs in which all vertices have degree 4 or 6. This gives an algorithm in quadratic time to determine whether a *-graph admits an embedding into the plane. [ABSTRACT FROM AUTHOR]

Norton and Sălăgean [Strong Gröbner bases and cyclic codes over a finite-chain ring, in Proc. Workshop on Coding and Cryptography, Paris, Electronic Notes in Discrete Mathematics, Vol. 6 (Elsevier Science, 2001), pp. 391-401] have presented an algorithm for computing Gröbner bases over finite-chain rings. Byrne and Fitzpatrick [Gröbner bases over Galois rings with an application to decoding alternant codes, J. Symbolic Comput. 31 (2001) 565-584] have simultaneously proposed a similar algorithm for computing Gröbner bases over Galois rings (a special kind of finite-chain rings). However, they have not incorporated Buchberger's criteria into their algorithms to avoid unnecessary reductions. In this paper, we propose the adapted version of these criteria for polynomials over finite-chain rings and we show how to apply them on Norton-Sălăgean algorithm. The described algorithm has been implemented in Maple and experimented with a number of examples for the Galois rings. [ABSTRACT FROM AUTHOR]

As Dempster-Shafer theory spreads in different application fields, and as mass functions are involved in more and more complex systems, the need for algorithms randomly generating mass functions arises. Such algorithms can be used, for instance, to evaluate some statistical properties or to simulate the uncertainty in some systems (e.g., data base content, training sets). As such random generation is often perceived as secondary, most of the proposed algorithms use straightforward procedures whose sample statistical properties can be difficult to characterize. Thus, although such algorithms produce randomly generated mass functions, they do not always produce what could be expected from them (for example, uniform sampling in the set of all possible mass functions). In this paper, we briefly review some well-known algorithms, explaining why their statistical properties are hard to characterize. We then provide relatively simple algorithms and procedures to perform efficient random generation of mass functions whose sampling properties are controlled. [ABSTRACT FROM AUTHOR]

In this paper we survey recent developments in the theory of groups acting on A-trees. We are trying to unify all significant methods and techniques, both classical and recently developed, in an attempt to present various faces of the theory and to show how these methods can be used to solve major problems about finitely presented A-free groups. Besides surveying results known up to date we draw many new corollaries concerning structural and algorithmic properties of such groups. [ABSTRACT FROM AUTHOR]

Escape time algorithm is a classical algorithm to calculate the Julia sets, but it has the disadvantage of dull color and cannot record the iterative process of the points. In this paper, we present the equipotential point algorithm to calculate the Julia sets by recording the strike frequency of the points in the iterative process. We calculate and analyze the Julia sets in the complex plane by using this algorithm. Finally, we discuss the iteration trajectory of a single point. [ABSTRACT FROM AUTHOR]

Most dimensionality reduction methods depend significantly on the distance measure used to compute distances between different examples. Therefore, a good distance metric is essential to many dimensionality reduction algorithms. In this paper, we present a new dimensionality reduction method for data visualization, called Distance-ratio Preserving Embedding (DrPE), which preserves the ratio between the pairwise distances. It is achieved by minimizing the mismatch between the distance ratios derived from input and output space. The proposed method can preserve the relational structures among points of the input space. Extensive visualization experiments compared with existing dimensionality reduction algorithms demonstrate the effectiveness of our proposed method. [ABSTRACT FROM AUTHOR]

Many modern classification tasks are defined in highly-dimensional feature spaces. The derivation of high-performing genetic fuzzy rule-based classification systems (GFRBCSs) in such scenarios is a non-trivial task. This paper presents a framework for increasing the performance of GFRBCSs by creating a hierarchical fuzzy rule-based classifier. The proposed system is constructed through repeated invocations to a base GFRBCS procedure, considering at each step an input space fuzzy partition of a certain granularity. The best performing rules are inserted in the hierarchical rule base and the process is repeated again, considering a thicker granularity. The employed boosting scheme guides the algorithm in creating new rules to treat uncovered or misclassified patterns, thus monotonically increasing the performance of the classifier. Extensive experimental analysis in a number of real-world high-dimensional classification tasks proves the effectiveness of the proposed approach in increasing the performance of the base classifier, maintaining its interpretability to a considerable degree. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a natural variation of the problem of computing all bichro-matic intersections between two sets of segments. Given two sets R and B of n points in the plane defining two sets of segments, say red and blue, we present an O(n²) time and space algorithm for solving the problem of reporting the set of segments of each color intersected by segments of the other color. We also prove that this problem is 3-Sum hard and provide some illustrative examples of several point configuration. [ABSTRACT FROM AUTHOR]

The handoff rate is identified in a hybrid channel allocation algorithm of a wireless and mobile network. In this network model, both new calls and handoff calls to a cell have possibilities to borrow channels from the control center if all allocated channels to the cell are used up. In addition, there is a buffer with finite size reserved exclusively for handoff calls in a cell when they arrived but are not be able to borrow channels from the control center. In this paper, we derived a novel and theoretical expression of the handoff rate in the network first. This analytical expression for handoff rate is a general form which covers several special cases discussed in the literature. Then, an efficient iterative algorithm to calculate this handoff rate is proposed also. By using this algorithm, the handoff rate and the blocking probability of both new calls and handoff calls will be successfully derived at the same time. Furthermore, our numerical analysis validates the algorithm and the corresponding theoretic expression. [ABSTRACT FROM AUTHOR]

The Linear Time Frequency Analysis Toolbox is a MATLAB/Octave toolbox for computational time-frequency analysis. It is intended both as an educational and computational tool. The toolbox provides the basic Gabor, Wilson and MDCT transform along with routines for constructing windows (filter prototypes) and routines for manipulating coefficients. It also provides a bunch of demo scripts devoted either to demonstrating the main functions of the toolbox, or to exemplify their use in specific signal processing applications. In this paper we describe the used algorithms, their mathematical background as well as some signal processing applications. [ABSTRACT FROM AUTHOR]

The paper addresses the enumeration problem for k-tangles. We introduce the notion of a cascade diagram of a k-tangle projection and suggest an effective enumeration algorithm for projections based on the cascade representation. Tangle projections and alternating tangles with up to 12 crossings are tabulated. We also provide pictures of alternating k-tangles with at most five crossings. [ABSTRACT FROM AUTHOR]

The complexity status of the minimum r-star cover problem for orthogonal polygons had been open for many years, until 2004 when Ch. Worman and J. M. Keil proved it to be polynomially tractable (Polygon decomposition and the orthogonal art gallery problem, IJCGA 17(2) (2007), 105-138). However, since their algorithm has Õ(n17)-time complexity, where Õ(·) hides a polylogarithmic factor, and thus it is not practical, in this paper we present a linear-time 3-approximation algorithm. Our approach is based upon the novel partition of an orthogonal polygon into so-called o-star-shaped orthogonal polygons. [ABSTRACT FROM AUTHOR]

In this paper, we prove that any finite or infinite family of squares with total area at most 1 can be packed into the rectangle with dimensions and that this rectangle is unique with this property and minimum area. Furthermore, we show that for a finite unit family of n squares which are given sorted by their side lengths, a packing into the rectangle can be found in linear time, which yields an O(n n) time algorithm for the general case. With a restriction to finite unit families, the former statement has been published by D. J. Kleitman and M. Krieger, who - as they state themselves - only provide "a general discussion of the methods used [throughout the proof] and an outline of the major cases". Although they refer their proof to as "being constructive", it is not clear from their presentation how a packing algorithm would look like. Regarding the fact that there are some other results that rely on this statement - some of which even make use of a corresponding packing algorithm - it is important to have an complete and preferably constructive published proof for it. The proof that is presented here is constructive and uses an interesting technique based on quadratic programming which could be applicable to other packing problems as well. [ABSTRACT FROM AUTHOR]

Büchi's square problem asks if there exists a positive integer M such that all x1, ..., xM ∈ ℤ satisfying the equations $x_{r-2}^2-2x_{r-1}^2+x_{r}^2 = 2$ for all 3 ≤ r ≤ M must also satisfy $x_r^2 = (x+r)^2$ for some integer x and for all 1 ≤ r ≤ M. Hensley's problem asks if there exists a positive integer M such that, for any integers ν and a, if (ν + r)2 - a is a square for all 1 ≤ r ≤ M, then a = 0. It is not difficult to see that a positive answer to Hensley's problem implies a positive answer to Büchi's square problem. One can ask a more general version of Hensley's problem by replacing the square power by an nth power for any integer n ≥ 2 which is called Hensley's problem for nth powers. In this paper, we will study Hensley's problem for nth powers over function fields of any characteristic. [ABSTRACT FROM AUTHOR]

Let P be a simple polygon of n vertices and let S be a set of N points lying in the interior of P. A geodesic diskGD(p,r) with center p and radius r is the set of points in P that have a geodesic distance ≤ r from p (where the geodesic distance is the length of the shortest polygonal path connection that lies in P). In this paper we present an output sensitive algorithm for finding all N geodesic disks centered at the points of S, for a given value of r. Our algorithm runs in $O((n+(kn)^{\frac{2}{3}}+k)\log^cn)$ time, for some constant c and output size k. It is the basis of a cluster reporting algorithm where geodesic distances are used. [ABSTRACT FROM AUTHOR]

Document clustering is one of the most effective techniques to organize documents in an unsupervised manner. In this paper, an Incremental method for document Clustering based on Information Bottleneck theory (ICIB) is presented. The ICIB is designed to improve the accuracy and efficiency of document clustering, and resolve the issue that an arbitrary choice of document similarity measure could produce an inaccurate clustering result. In our approach, document similarity is calculated using information bottleneck theory and documents are grouped incrementally. A first document is selected randomly and classified as one cluster, then each remaining document is processed incrementally according to the mutual information loss introduced by the merger of the document and each existing cluster. If the minimum value of mutual information loss is below a certain threshold, the document will be added to its closest cluster; otherwise it will be classified as a new cluster. The incremental clustering process is low-precision and order-dependent, which cannot guarantee accurate clustering results. Therefore, an improved sequential clustering algorithm (SIB) is proposed to adjust the intermediate clustering results. In order to test the effectiveness of ICIB method, ten independent document subsets are constructed based on the 20NewsGroup and Reuters-21578 corpora. Experimental results show that our ICIB method achieves higher accuracy and time performance than K-Means, AIB and SIB algorithms. [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 introduce the notion of m-irreducibility that extends the standard concept of irreducibility of a numerical semigroup when the multiplicity is fixed. We analyze the structure of the set of m-irreducible numerical semigroups, we give some properties of these numerical semigroups and we present algorithms to compute the decomposition of a numerical semigroup with multiplicity m into m-irreducible numerical semigroups. [ABSTRACT FROM AUTHOR]

Given a set T of n points in ℝ2, a Manhattan network on T is a graph G = (V,E) with the property that all the edges in E are vertical or horizontal line segments connecting points in V ⊇ T and for all p, q ∈ T, the graph contains a path having the length exactly L1 distance between p and q. The Minimum Manhattan Network problem is to find a Manhattan network of minimum length, i.e. minimizing the total length of the line segments of the network. In this paper we present a 2-approximation algorithm with time complexity O(n log n), which improves over a recent combinatorial 2-approximation algorithm with running time O(n2). Moreover, compared with other 2-approximation algorithms using linear programming or dynamic programming techniques, we show that a greedy strategy suffices to obtain a 2-approximation algorithm. [ABSTRACT FROM AUTHOR]

Currently, two-dimensional dyadic wavelet transform (2D-DWT) is habitually considered as the one presented by Mallat, which is defined by an approximation component, two detail components in horizontal and vertical directions. This paper is to introduce a new type of two-dimensional dyadic wavelet transform and its application so that dyadic wavelet can be studied and used widely furthermore. (1) Two-dimensional stationary dyadic wavelet transform (2D-SDWT) is proposed, it is defined by approximation coefficients, detail coefficients in horizontal, vertical and diagonal directions, which is essentially the extension of two-dimensional stationary wavelet transform for orthogonal/biorthogonal wavelet filters. (2) ε-decimated dyadic discrete wavelet transform (DDWT) is introduced and its relation with 2D-SDWT is given, where ε is a sequence of 0's and 1's. (3) Mallat decomposition algorithm based on dyadic wavelet is introduced as a special case of ε-decimated DDWT, and so a face recognition algorithm based on dyadic wavelet is proposed, and experimental results are given to show its effectiveness. [ABSTRACT FROM AUTHOR]

In this paper, we describe an algorithm for computing biorthogonal compactly supported dyadic wavelets related to the Walsh functions on the positive half-line ℝ+. It is noted that a similar technique can be applied in very general situations, e.g., in the case of Cantor and Vilenkin groups. Using the feedback-based approach, some numerical experiments comparing orthogonal and biorthogonal dyadic wavelets with the Haar, Daubechies, and biorthogonal 9/7 wavelets are prepared. [ABSTRACT FROM AUTHOR]

It is known by few that a trivial knot can be transformed into a lattice knot whose three shadows are all trees (here, three shadows mean the projections of the lattice knot to the directions of ordinary orthogonal axes). Since a knot itself is a loop in the space, this fact may be rather astonishing. It will be interesting to ask whether a non-trivial knot has such a transformation or not. The purpose of this paper is to show that any two-bridge torus knot or link has a transformation into a lattice knot whose three shadows are all trees. The algorithm to construct such a position will be demonstrated. [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]

In this paper, we give an algorithm to calculate the minimal self-intersection number of paths in a compact surface with boundary representing a given element of the free group F(x1, x2, ..., xn). In particular, this algorithm says whether or not a word in x1, x2, ..., xn is representable by a simple path. Our algorithm is simpler than similar algorithms given previously. In the case of a disk with n holes the problem is equivalent to the problem of deciding which relators can appear in an Artin n-presentation. [ABSTRACT FROM AUTHOR]

We introduce the peak normal form for elements of the Baumslag-Solitar groups BS(p,q). This normal form is very close to the length-lexicographical normal form, but more symmetric. Both normal forms are geodesic. This means the normal form of an element u-1v yields the shortest path between u and v in the Cayley graph. For horocyclic elements the peak normal form and the length-lexicographical normal form coincide. The main result of this paper is that we can compute the peak normal form in polynomial time if p divides q. As consequence we can compute geodesic lengths in this case. In particular, this gives a partial answer to Question 1 in [4] For arbitrary p and q it is possible to compute the peak normal form (length-lexicographical normal form resp.) also the for elements in the horocyclic subgroup and, more generally, for elements which we call hills. This approach leads to a linear time reduction of the problem of computing geodesics to the problem of computing geodesics for Britton-reduced words where the t-sequence starts with t-1 and ends with t. [ABSTRACT FROM AUTHOR]

The problem of extracting a basis of irredundant motifs from a sequence is considered. In previous work such bases were built incrementally for all suffixes of the input string s in O(n3), where n is the length of s. Faster, non-incremental algorithms have been based on the landmark approach to string searching due to Fischer and Paterson, and exhibit respective time bounds of O(n2log n log|Σ|) and O(|Σ|n2log2 n log log n), with Σ denoting the alphabet. The algorithm by Fischer and Paterson makes crucial use of the FFT, which is impractical with long sequences. The present paper describes an off-line algorithm for binary strings that takes O(n2) time. The algorithm does not need to resort to the FFT and yet its performance is optimal for finite Σ. [ABSTRACT FROM AUTHOR]

This paper proposes a concurrent implementation of a background subtraction algorithm suitable for monochromatic video sequences. In the training period, a set of frames is used to determine an estimate of the scene background, as well as background noise. In the test period, each new frame of the video sequence is compared to the background model, and foreground objects are obtained taking into account the background noise estimate. Shadows and highlights are also detected and removed. Concurrent programming tools and techniques, such as multithreading, are used to implement a concurrent solution for this problem, and combined with other optimization tools (such as destination word accumulation for morphological operators and the use of lookup tables for shadow detection/removal) to achieve the highest frame rate possible. Experimental results comprise a comparison of the performance including progressively each optimization tool, and they show that the fully optimized algorithm is much faster than a naive sequential implementation. Also, experiments performed on two-way processor and on dual-core processor computers indicate that the proposed algorithm is suited for the recent multi-core technology. [ABSTRACT FROM AUTHOR]

The optimization of many engineering systems is challenged by the solution over-fit to the data set used to evaluate potential solutions during the evolutionary process. The solution over-fit phenomenon is hard to detect and is especially prevalent in problems involving example-based training, such as pattern feature selection and pattern classifier design. For these applications, uncontrolled over-fit can lead to biased features being extracted and degraded classifier generalization abilities. This paper details the performance of a solution over-fit control strategy used in the multiobjective evolutionary optimization of a multileveled classification system. This control, embedded within a solution validation procedure, minimizes the over-fit effects without modifying the dominance relation used in the processing of candidate solutions. Extensive experimental analysis using multiobjective genetic and memetic algorithms demonstrates both the need and the efficiency of the proposed over-fit control for pattern classification systems optimization. [ABSTRACT FROM AUTHOR]

This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automaton-based representation of the corresponding set of real vectors. The technique is quite general and has been implemented. [ABSTRACT FROM AUTHOR]

Analysis of infinitary safety properties with automated compositional reasoning through learning is discussed in the paper. We consider the class of intuitionistically closed regular languages and show that it forms a Heyting algebra and is finitely approximatable. Subsequently, compositional proof rules can be verified automatically and learning algorithms for finitary regular languages suffice. We also establish an axiom to deduce circular compositional proof rules for the infinitary languages. [ABSTRACT FROM AUTHOR]

In this paper, we study an interesting matrix decomposition problem that seeks to decompose a "complicated" matrix into two "simpler" matrices while minimizing the sum of the horizontal complexity of the first sub-matrix and the vertical complexity of the second sub-matrix. The matrix decomposition problem is crucial for improving the "step-and-shoot" delivery efficiency in Intensity-Modulated Radiation Therapy, which aims to deliver a highly conformal radiation dose to a target tumor while sparing the surrounding normal tissues. Our algorithm is based on a non-trivial graph construction scheme, which enables us to formulate the decomposition problem as computing a minimum s-t cut in a 3-D geometric multi-pillar graph. Experiments on randomly generated intensity map matrices and on clinical data demonstrated the efficacy of our algorithm. [ABSTRACT FROM AUTHOR]

This paper shows an algorithm which computes the law of the Lie algebra associated with the complex Lie group of n × n upper-triangular matrices with exponential elements in their main diagonal. For its implementation two procedures are used, respectively, to define a basis of the Lie algebra and the nonzero brackets in its law with respect to that basis. These brackets constitute the final output of the algorithm, whose unique input is the matrix order n. Besides, its complexity is proved to be polynomial and some complementary computational data relative to its implementation are also shown. [ABSTRACT FROM AUTHOR]

In this paper, we present efficient geometric algorithms for the discrete constrained 1-D K-means clustering problem and extend our solutions to the continuous version of the problem. One key clustering constraint we consider is that the maximum difference in each cluster cannot be larger than a given threshold. These constrained 1-D K-means clustering problems appear in various applications, especially in intensity-modulated radiation therapy (IMRT). Our algorithms improve the efficiency and accuracy of the heuristic approaches used in clinical IMRT treatment planning. [ABSTRACT FROM AUTHOR]

For constrained optimization problems, evolutionary algorithms often utilize a penalty function to deal with constraints, even if it is difficult to control the penalty parameters. To overcome this shortcoming, this paper presents a new penalty function which has no parameter and can effectively handle constraint first, after which a hybrid-fitness function integrating this penalty function into the objective function is designed. The new fitness function can properly evaluate not only feasible solution, but also infeasible one, and distinguish any feasible one from an infeasible one. Meanwhile, a new crossover operator based on simplex crossover operator and a new PSO mutation operator are also proposed, which can produce high quality offspring. Based on these, a new evolutionary algorithm for constrained optimization problems is proposed. The simulations are made on ten widely used benchmark problems, and the results indicate the proposed algorithm is effective. [ABSTRACT FROM AUTHOR]

In this paper we present a division theorem for the pseudovariety of semigroups 햮햣 (햮햱) generated by all semigroups of order-preserving or order-reversing (orientation-preserving or orientation-reversing) full transformations on a finite chain. [ABSTRACT FROM AUTHOR]

Traditional supervised classification algorithms require a large number of labelled examples to perform accurately. Semi-supervised classification algorithms attempt to overcome this major limitation by also using unlabelled examples. Unlabelled examples have also been used to improve nearest neighbour text classification in a method called bridging. In this paper, we propose the use of bridging in a semi-supervised setting. We introduce a new bridging algorithm that can be used as a base classifier in most semi-supervised approaches. We empirically show that the classification performance of two semi-supervised algorithms, self-learning and co-training, improves with the use of our new bridging algorithm in comparison to using the standard classifier, JRipper. We propose a similarity metric for short texts and also study the performance of self-learning with a number of instance selection heuristics. [ABSTRACT FROM AUTHOR]

Although there are lots of methods to analyze chaotic systems, they tend to be of local nature and reveal only limited information about a certain group of control parameters. This paper explores a visualization technique on the basis of Mandelbrot set (M-set) methodology to give an overall view of a chaotic system's dynamical performance in the parameter space. Firstly, the Lyapunov spectra with regard to different points in the parameter space are calculated, according to which the color of these points is defined. Then points in the given parameter space are mapped to the computer screen and a colorful image named Lyapunov distribution map (LDM) is generated, which conveys a wealth of information about a system's dynamic behavior across variations in its control parameters. The results of visualizing two typical chaotic systems proved the feasibility and validity of this technique. The study suggests that desired dynamical performance of a system can be conveniently achieved by selecting a point from some color region in its LDM and adjusting the control parameters according to the point value. Furthermore, there is no need for any prior knowledge of the system under evaluation and the complicated mathematical analysis before the formulation of appropriate rules for a new system can also be avoided since uniform rules are employed in the classification of parameter points for any system and the LDM is generated via the same algorithm. [ABSTRACT FROM AUTHOR]

Stationary wavelet transform is an efficient algorithm for remote sensing image fusion. In this paper, we investigate the effects of orthogonal/biorthogonal filters and decomposition depth on using stationary wavelet analysis for fusion. Spectral discrepancy and spatial distortion are used as quality measures. Empirical results lead to some recommendations on the wavelet filter parameters for use in remote sensing image fusion applications. [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]

Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called Deutsch's problem. Consider a Boolean function f: {0,1} → {0,1} and suppose that we have a (classical) black box to compute it. The problem asks whether f is constant [that is, f(0) = f(1)] or balanced [f(0) ≠ f(1)]. Classically, to solve the problem seems to require the computation of f(0) and f(1), and then the comparison of results. Is it possible to solve the problem with only one query on f? In a famous paper published in 1985, Deutsch posed the problem and obtained a "quantum" partial affirmative answer. In 1998, a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello and Mosca. Here we will show that the quantum solution can be de-quantized to a deterministic simpler solution which is as efficient as the quantum one. The use of "superposition," a key ingredient of quantum algorithm, is — in this specific case — classically available. [ABSTRACT FROM AUTHOR]

We present a convergence study for a hybrid Lattice Boltzmann-Molecular Dynamics model for the simulation of dense liquids. Time and length scales are decoupled by using an iterative Schwarz domain decomposition algorithm. The velocity field from the atomistic domain is introduced as forcing terms to the Lattice Boltzmann model of the continuum while the mean field of the continuum imposes mean field conditions for the atomistic domain. In the present paper we investigate the effect of varying the size of the atomistic subdomain in simulations of two dimensional flows of liquid argon past carbon nanotubes and assess the efficiency of the method. [ABSTRACT FROM AUTHOR]