Search

Abstract Traditional dynamic multiobjective evolutionary algorithms usually imitate the evolution of nature, maintaining diversity of population through different strategies and making the population track the Pareto optimal solution set efficiently after the environmental change. However, these algorithms neglect the role of the dynamic environment in evolution, leading to the lacking of active guieded search. In this paper, a dynamic multiobjective evolutionary algorithm based on a dynamic evolutionary environment model is proposed (DEE-DMOEA). When the environment has not changed, this algorithm makes use of the evolutionary environment to record the knowledge and information generated in evolution, and in turn, the knowledge and information guide the search. When a change is detected, the algorithm helps the population adapt to the new environment through building a dynamic evolutionary environment model, which enhances the diversity of the population by the guided method, and makes the environment and population evolve simultaneously. In addition, an implementation of the algorithm about the dynamic evolutionary environment model is introduced in this paper. The environment area and the unit area are employed to express the evolutionary environment. Furthermore, the strategies of constraint, facilitation and guidance for the evolution are proposed. Compared with three other state-of-the-art strategies on a series of test problems with linear or nonlinear correlation between design variables, the algorithm has shown its effectiveness for dealing with the dynamic multiobjective problems. [ABSTRACT FROM AUTHOR]

In this paper, a novel algorithm of the grey model termed GME(1,1 ) is proposed. Based on the discrete form of developing coefficients â of grey model, the new grey modeling method is presented. The paper raises some numerical examples and real physical eases for model verification test. It is evident that the proposed approach can correct the defects of the original grey model and reduce the affects of the extreme value of monitoring data. It validates the superiority of the proposed approach. [ABSTRACT FROM AUTHOR]

The goal of this paper is to further the investigation begun in Chalmers and Prophet, Numer. Funct. Anal. Optimiz. 1997; 18:507–520. With the benefit of nearly 10 years of work, we begin by indicating how several proofs from Chalmers and Prophet, Numer. Funct. Anal. Optimiz. 1997; 18:507–520, can be substantially improved. We show that the problem of preserving k-convexity onto Πn is one part of a larger shape-preserving problem (multiconvex preservation) relative to Πn, and we completely solve this expanded problem. And finally, we demonstrate that multiconvex preserving projections constructed in this paper are in fact of minimal operator norm in a large class of Banach spaces. [ABSTRACT FROM AUTHOR]

Abstract: The present paper describes an efficient algorithm to integrate the equations of motion implicitly in the frequency domain. The standard FEM displacement model (Galerkin formulation) is employed to perform space discretization, and the time-marching process is carried out through an algorithm based on the Green’s function of the mechanical system in nodal coordinates. In the present formulation, mechanical system Green’s functions are implicitly calculated in the frequency domain. Once the Green’s functions related matrices are computed, a time integration procedure, which demands low computational effort when applied to non-linear mechanical systems, becomes available. At the end of the paper numerical examples are presented in order to illustrate the accuracy of the present approach. [Copyright &y& Elsevier]

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 studies the limiting behavior of weighted infeasible central paths for semidefinite programming (SDP) obtained from centrality equations of the form X½ SX½ = vW, where W is a fixed positive definite matrix and v>0 is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. It is shown that a weighted central path as a function of √v can be extended analytically beyond 0 and hence that the path converges as v↓0. Characterization of the limit points of the path and its normalized first-order derivatives are also provided. As a consequence, it is shown that a weighted central path can have two types of behavior: it converges either as &Tetha;(v) or asT &Tetha;(√v) depending on whether the matrix W on a certain scaled space is block diagonal or not, respectively. We also derive an error bound on the distance between a point lying in a certain neighborhood of the central path and the set of primal-dual optimal solutions. Finally, in light of the results of this paper, we give a characterization of a sufficient condition proposed by Potra and Sheng which guarantees the superlinear convergence of a class of primal-dual interior-point SDP algorithms. [ABSTRACT FROM AUTHOR]

This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming (SDP) obtained from centrality equations of the form X½ SX½ = vW, where W is a fixed positive definite matrix and v>0 is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. It is shown that a weighted central path as a function of √v can be extended analytically beyond 0 and hence that the path converges as v↓0. Characterization of the limit points of the path and its normalized first-order derivatives are also provided. As a consequence, it is shown that a weighted central path can have two types of behavior: it converges either as &Tetha;(v) or asT &Tetha;(√v) depending on whether the matrix W on a certain scaled space is block diagonal or not, respectively. We also derive an error bound on the distance between a point lying in a certain neighborhood of the central path and the set of primal-dual optimal solutions. Finally, in light of the results of this paper, we give a characterization of a sufficient condition proposed by Potra and Sheng which guarantees the superlinear convergence of a class of primal-dual interior-point SDP algorithms. [ABSTRACT FROM AUTHOR]

The aim of this paper is to exploit the algorithms of paper Experimental Math. 8 (1999) in order to produce a new algebraic method for computing efficiently absolute Lagrange resolvent, a fundamental tool in constructive algebraic Galois theory. This article is composed of two parts.The main idea of the first part is to break up the calculation of absolute resolvent into smaller computations. Since a multi-resolvent is a factor of a resolvent, the whole resolvent may be computed by means of several multi-resolvents.The idea of the second part is that an irreducible polynomial over Z might be reducible over Z /pZ for certain integer p. So the first part can be applied and then, the Chinese remainder theorem allows to lift up the resolvent over Z. [Copyright &y& Elsevier]

This paper presents RULES-5, a new induction algorithm for effectively handling problems involving continuous attributes. RULES-5 is a 'covering' algorithm that extracts IF–THEN rules from examples presented to it. The paper first reviews existing methods of rule extraction and dealing with continuous attributes. It then describes the techniques adopted for RULES-5 and gives a step-by-step example to illustrate their operation. The paper finally gives the results of applying RULES-5 and other algorithms to benchmark problems. These clearly show that RULES-5 generates rule sets that are more accurate than those produced by its immediate predecessor RULES-3 Plus and by a well-known commercially available divide-and-conquer machine learning algorithm. [ABSTRACT FROM AUTHOR]

This paper gives a bibliographical review of the finite element and boundary element parallel processing techniques from the theoretical and application points of view. Topics include: theory - domain decomposition/partitioning, load balancing, parallel solvers/algorithms, parallel mesh generation, adaptive methods, and visualization/graphics; applications - structural mechanics problems, dynamic problems, material/geometrical non-linear problems, contact problems, fracture mechanics, field problems, coupled problems, sensitivity and optimization, and other problems; hardware and software environments - hardware environments, programming techniques, and software development and presentations. The bibliography at the end of this paper contains 850 references to papers, conference proceedings and theses/dissertations dealing with presented subjects that were published between 1996 and 2002. [ABSTRACT FROM AUTHOR]

The implicitly shifted (bulge-chasing) QZ algorithm is the most popular method for solving the generalized eigenvalue problem Av = λBv. This paper explains why the QZ algorithm functions well even in the presence of infinite eigenvalues. The key to rapid convergence of QZ (and QR) algorithms is the effective transmission of shifts during the bulge chase. In this paper the mechanism of transmission of shifts is identified, and it is shown that this mechanism is not disrupted by the presence of infinite eigenvalues. Both the QZ algorithm and the preliminary reduction to Hessenberg-triangular form tend to push the infinite eigenvalues toward the top of the pencil. Thus they should be deflated at the top. [ABSTRACT FROM AUTHOR]

This paper notes the fact that the recording code often takes the form of a multitrack code, as well as the fact that the k-constraint in the (d, k)-constraint is considerably relaxed, which increases the capacity. Then the paper proposes a systematic construction algorithm for the fixed block-length multitrack (d, k) code and discusses the coding characteristics. A simple idea is applied in the code construction to apply the (d, ∞) code to all tracks except for one in order to reflect the relaxation of the k-constraint on the improvement of the coding rate. The (d, ∞) code is applied to the left track if the vector obtained by the elementwise logical sum of the code words satisfies the k-constraint and, if not, the (d, k) code is applied. The author has already proposed a systematic construction algorithm for the efficient fixed block-length (d, k) code. This paper discusses mainly the systematic construction algorithm and the coding characteristics for the fixed block-length (d, ∞) code, based on the unique ordering technique of the binary sequence by the Schalkwijk algorithm, as the systematic construction algorithm for the fixed block-length multitrack (d, k) code based on the forementioned idea. The coding rate and the coding efficiency are examined, and the result indicates that the characteristics are very close to those of the (d, ∞) code. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of determining a sequence for processing jobs on a machine, with sequence dependent setup times, such that the total flow time is minimized. The paper includes a branch and bound algorithm to find the optimal tour sequence. [ABSTRACT FROM AUTHOR]

Derive the quantitative predictions of constraint-based models require of conversion algorithms to enumerate and construct the skeleton graph conformed by the extreme points of the feasible region, where all constraints in the model are fulfilled. The conversion is problematic when the system of linear constraints is degenerate. This paper describes a conversion algorithm that combines the best of two methods: the incremental slicing of cones that defeats degeneracy and pivoting for a swift traversal of the set of extreme points. An extensive computational practice uncovers two complementary classes of conversion problems. The two classes are distinguished by a practical measure of complexity that involves the input and output sizes. Detailed characterizations of the complexity classes and the corresponding performances of the algorithm are presented. For the benefit of implementors, a simple example illustrates the stages of the exposition. [ABSTRACT FROM AUTHOR]

In this paper, we consider the half-integral disjoint paths packing. For a graph G and k pairs of vertices (s1, t1), (s2, t2), …, (sk, tk) in G, the objective is to find paths P1, …, Pk in G such that Pi joins si and ti for i = 1, 2, …, k, and in addition, each vertex is on at most two of these paths. We give a polynomial-time algorithm to decide the feasibility of this problem with k = O((log n/log log n)1/7). This improves a result by Kleinberg [Proceedings of the 30th ACM Symposium on Theory of Computing, 1998, pp 530-539] who proved the same conclusion when k = O((log log n)2/15). Our algorithm still works for several problems related to the bounded unsplittable flow. These results can all carry over to problems involving edge capacities. Our main technical contribution is to give a "crossbar" of a polynomial size of the tree width of the graph. [ABSTRACT FROM AUTHOR]

A new optimum approach is presented for strapdown coning algorithm design based on Explicit matching of desired response to expected coning input magnitude as a function of coning frequency. Unlike previous time or frequency Taylor series expansion techniques, the new method achieves optimization through minimum least-squares estimation over a user selected design frequency range. The error being minimized is the square of the weighted algorithm error, the weighting factor being user specified coning amplitude over frequency. This methodology allows the coning algorithm coefficients to be independently designed for each caning axis to achieve optimal balanced performance over the frequency range of expected coning inputs. Performance of the new algorithm design technique is evaluated by comparison with previous time and frequency-series approaches, in discrete and stochastic coning environments, and over a time based extreme dynamic maneuvering profile. A generalized method is presented for translating system performance requirements into expected coning amplitude versus frequency profiles for calculating Explicit algorithm coefficients, and for evaluating coning algorithm accuracy. The paper includes derivations of generalized formulas for calculating algorithm coefficients for previous time and frequency-series design approaches. [ABSTRACT FROM AUTHOR]

In this paper, we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. An instance of this problem consists of a set of k people and m indivisible goods. Each person has a known linear utility function over the set of goods which might be different from the utility functions of other people. The goal is to distribute the goods among the people and maximize the minimum utility received by them. The approximation ratio of our algorithm is Ω(1/√k log3 k). As a crucial part of our algorithm, we design and analyze an iterative method for rounding a fractional matching on a tree which might be of independent interest. We also provide better bounds when we are allowed to exclude a small fraction of the people from the problem. [ABSTRACT FROM AUTHOR]

A possible way to accelerate the execution of a program is to optimize it at compilation time. Some optimizing transformations use additional information obtained by a preliminary analysis of the program. The paper is devoted to the popular method of the analysis of the intermediate program representation called the value numbering method. Several techniques improving the classical algorithm are proposed and the effect the proposed improvements on the execution time of certain programs is analyzed. [ABSTRACT FROM AUTHOR]

Given a graph G=( V, E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 l kT( n, m)) time and Vertex Multiterminal Cut can be solved in O( k l T( n, m)) time, where T( n, m)= O(min ( n2/3, m1/2) m) is the running time of finding a minimum ( s, t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 l T( n, m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 l T( n, m)), O(2.772 l T( n, m)), O(3.349 l T( n, m)) and O(3.857 l T( n, m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: $O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m))$ -time algorithm for Edge Multicut and O((2 k) k+ l/2 T( n, m))-time algorithm for Vertex Multicut. [ABSTRACT FROM AUTHOR]

This paper shows how to compute O(√log n)-approximations to the Sparsest Cut and Balanced Separator problems in Õ(n²) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires Õ (n9.5) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. [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]

The present paper proposes a novel stereo algorithm utilizing multi-sets of reaction–diffusion equations. The problem of detecting a stereo disparity map becomes the segmentation problem, in which the uniqueness assumption and the continuity assumption on disparity distribution are taken into account. A set of reaction–diffusion equations realizes the continuity assumption, while a mutual-inhibition mechanism among the multi-sets realizes the uniqueness one. In addition, each set of equations has a self-inhibition mechanism, which is necessary for the reaction-diffusion equations applied to stereo disparity detection. Performance of the proposed algorithm is evaluated for well-known test stereo images. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we analyze O''Hara''s partition bijection. We present three type of results. First, we show that O''Hara''s bijection can be viewed geometrically as a certain scissor congruence type result. Second, we obtain a number of new complexity bounds, proving that O''Hara''s bijection is efficient in several special cases and mildly exponential in general. Finally, we prove that for identities with finite support, the map of the O''Hara''s bijection can be computed in polynomial time, i.e. much more efficiently than by O''Hara''s construction. [Copyright &y& Elsevier]

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]

Abstract: In this paper, a subspace limited memory BFGS algorithm for solving large-scale bound constrained optimization problems is developed. It is modifications of the subspace limited memory quasi-Newton method proposed by Ni and Yuan [Q. Ni, Y.X. Yuan, A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization, Math. Comput. 66 (1997) 1509–1520]. An important property of our proposed method is that more limited memory BFGS update is used. Under appropriate conditions, the global convergence of the method is established. The implementations of the method on CUTE test problems are presented, which indicate the modifications are beneficial to the performance of the algorithm. [Copyright &y& Elsevier]

The security of most elliptic curve cryptosystems is based on the intractability of the Elliptic Curve Discrete Logarithm Problem (ECDLP). Such a problem turns out to be computationally unfeasible when elliptic curves are suitably chosen. This paper provides an algorithm to obtain cryptographically good elliptic curves from a given one. The core of such a procedure lies on the usage of successive chains of isogenies, visiting different volcanoes of isogenies which are located in different l-cordilleras. [ABSTRACT FROM AUTHOR]

Count data with excess zeros often occurs in areas such as public health, epidemiology, psychology, sociology, engineering, and agriculture. Zero-inflated Poisson (ZIP) regression and zero-inflated negative binomial (ZINB) regression are useful for modeling such data, but because of hierarchical study design or the data collection procedure, zero-inflation and correlation may occur simultaneously. To overcome these challenges ZIP or ZINB may still be used. In this paper, multilevel ZINB regression is used to overcome these problems. The method of parameter estimation is an expectation-maximization algorithm in conjunction with the penalized likelihood and restricted maximum likelihood estimates for variance components. Alternative modeling strategies, namely the ZIP distribution are also considered. An application of the proposed model is shown on decayed, missing, and filled teeth of children aged 12 years old. [ABSTRACT FROM AUTHOR]

Abstract: Tarski’s fixed point theorem guarantees the existence of a fixed point of an order-preserving function defined on a nonempty complete lattice [B. Knaster, Un théorème sur les fonctions d’ensembles, Annales de la Société Polonaise de Mathématique 6 (1928) 133–134; A. Tarski, A lattice theoretical fixpoint theorem and its applications, Pacific Journal of Mathematics 5 (1955) 285–309]. In this paper, we investigate several algorithmic and complexity-theoretic topics regarding Tarski’s fixed point theorem. In particular, we design an algorithm that finds a fixed point of when it is given as input and as an oracle. Our algorithm makes queries to when is a total order on . We also prove that when both and are given as oracles, any deterministic or randomized algorithm for finding a fixed point of makes an expected queries for some and . [Copyright &y& Elsevier]

Kolodko and Schoenmakers (2006) and Bender and Schoenmakers (2006) introduced a policy iteration that allows the achievement of a tight lower approximations of the price for early exercise options via a nested Monte Carlo simulation in a Markovian setting. In this paper we enhance the algorithm by a scenario selection method. It is demonstrated by numerical examples that the scenario selection can significantly reduce the number of inner simulations actually performed, and thus can greatly speed up the method (by up to a factor of 15 in some examples). Moreover, it is shown that the modified algorithm retains the desirable properties of the original, such as the monotone improvement property, termination after a finite number of iteration steps, and numerical stability. [ABSTRACT FROM AUTHOR]

This paper is dedicated to location problems on graphs. We propose a linear time algorithm for the 1-median problem on wheel graphs. Moreover, some general results for the 1-median problem are summarized and parametric median problems are investigated. These results lead to a solution method for the 2-median problem on cactus graphs, i.e., on graphs where no two cycles have more than one vertex in common. The time complexity of this algorithm is $$\mathcal O(n^2)$$ , where n is the number of vertices of the graph. [ABSTRACT FROM AUTHOR]

Abstract: For a canonical threefold X, we know for a sufficiently large n. When , there are few known results about the integer n. This paper introduces an algorithm for computing plurigenera. Furthermore, when is small, especially 1 and 2, plurigenera are computed. This produces for and for when . Also, for and for with 8 possible exceptional cases when . [Copyright &y& Elsevier]

Abstract: In this paper, properties of planar (2D) grids are addressed in a mathematical point of view, and a novel algorithm for recognizing distorted grids with perspective transformations is presented. The proposed approach contains three parts: (a) recognizing parameters of affinely distorted grids by fitting Gaussian mixture models (GMMs) to grid spectrums, (b) rebuilding the grid structures via a generating iteration based on the acquired parameters, and (c) eliminating nonlinear effects caused by perspective transformations with the median of infinite lines from local structures (MILLS) method. All parts are precise and robust to local distortions, the absence of elements, and outliers. The accuracy and robustness are demonstrated by quantitative statistics in experiments on synthesis grids and real grid images. [Copyright &y& Elsevier]

Abstract: In this paper we develop a new mathematical approach to the pattern formation problem in biology. This problem was first posed mathematically by A.M. Turing, however some principal questions were left open (for example, whether there exists a “universal” mathematical model that allows one to obtain any spatio-temporal patterns). Here we consider the pattern formation ability of some class of genetic circuits. First, we show that the genetic circuits are capable of generating arbitrary spatio-temporal patterns. Second, we give upper and lower bounds on the number of genes in a circuit generating a given pattern. A connection between the complexity of gene interaction and the pattern complexity is found. We investigate the stochastic stability of patterning algorithms. Results are consistent with experimental data. [Copyright &y& Elsevier]

A 0/±1 matrix is balanced if it does not contain a square submatrix with exactly two nonzero entries per row and per column in which the sum of all entries is 2 modulo 4. A 0/1 matrix is balanceable if its nonzero entries can be signed ±1 so that the resulting matrix is balanced. A signing algorithm due to Camion shows that the problems of recognizing balanced 0/±1 matrices and balanceable 0/1 matrices are equivalent. Conforti, Cornuéjols, Kapoor and Vušković gave an algorithm to test if a 0/±1 matrix is balanced. Truemper has characterized balanceable 0/1 matrices in terms of forbidden submatrices. In this paper we give an algorithm that explicitly finds one of these forbidden submatrices or shows that none exists. [ABSTRACT FROM AUTHOR]

Measurement of image or video quality is crucial for many image-processing algorithms, such as acquisition, compression, restoration, enhancement, and reproduction. Traditionally, image quality assessment (QA) algorithms interpret image quality as similarity with a "reference" or "perfect" image. The obvious limitation of this approach is that the reference image or video may not be available to the QA algorithm. The field of blind, or no-reference, QA, in which image quality is predicted without the reference image or video, has been largely unexplored, with algorithms focussing mostly on measuring the blocking artifacts. Emerging image and video compression technologies can avoid the dreaded blocking artifact by using various mechanisms, but they introduce other types of distortions, specifically blurring and ringing. In this paper, we propose to use natural scene statistics (NSS) to blindly measure the quality of images compressed by JPEG2000 (or any other wavelet based) image coder. We claim that natural scenes contain nonlinear dependencies that are disturbed by the compression process, and that this disturbance can be quantified and related to human perceptions of quality. We train and test our algorithm with data from human subjects, and show that reasonably comprehensive NSS models can help us in making blind, but accurate, predictions of quality. Our algorithm performs close to the limit imposed on useful prediction by the variability between human subjects. [ABSTRACT FROM AUTHOR]

Abstract: In this paper the integration formulas of Newton Cot’s methods with positive coefficient for fuzzy integrations in [T. Allahviranloo, Newton Cot’s methods for integration of fuzzy functions, in press] are considered and then are followed by Romberg integration to obtain improvements of the approximations of fuzzy integrations. The proposed algorithm is illustrated by solving some numerical examples. [Copyright &y& Elsevier]

Abstract: In many applications of temporal reasoning we are interested in processing temporal information incrementally. In particular, given a set of temporal constraints (a temporal CSP) and a new constraint, we want to maintain certain properties of the extended temporal CSP (e.g., a solution), rather than recomputing them from scratch. The Point Algebra (PA) and the Interval Algebra (IA) are two well-known frameworks for qualitative temporal reasoning. The reasoning algorithms for PA and the tractable fragments of IA, such as Nebel and Bürckert''s maximal tractable class of relations (ORD-Horn), have originally been designed for “static” reasoning. In this paper, we study the incremental version of the fundamental reasoning problems in the context of these tractable classes. We propose a collection of new polynomial algorithms that can amortize their complexity when processing a sequence of input constraints to incrementally decide satisfiability, to maintain a solution, or to update the minimal representation of the CSP. Our incremental algorithms improve the total time complexity of using existing static techniques by a factor of or , where n is the number of the variables involved by the temporal CSP. An experimental analysis focused on constraints over PA confirms the computational advantage of our incremental approach. [Copyright &y& Elsevier]

Kernel-based linear-threshold algorithms, such as support vector machines and Perceptron-like algorithms, are among the best available techniques for solving pattern classification problems. In this paper, we describe an extension of the classical Perceptron algorithm, called second-order Perceptron, and analyze its performance within the mistake bound model of on-line learning. The bound achieved by our algorithm depends on the sensitivity to second-order data information and is the best known mistake bound for (efficient) kernel-based linear-threshold classifiers to date. This mistake bound, which strictly generalizes the well-known Perceptron bound, is expressed in terms of the eigenvalues of the empirical data correlation matrix and depends on a parameter controlling the sensitivity of the algorithm to the distribution of these eigenvalues. Since the optimal setting of this parameter is not known a priori, we also analyze two variants of the second-order Perceptron algorithm: one that adaptively sets the value of the parameter in terms of the number of mistakes made so far, and one that is parameterless, based on pseudoinverses. [ABSTRACT FROM AUTHOR]

Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs. We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension, then the property has an efficient tester. We apply our framework to a variety of problems. We present efficient property testing algorithms for geometric clustering problems, for the reversal distance problem, and for graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way, and the obtained complexity bounds either match or improve the previously known bounds. Furthermore, even if the asymptotic complexity of the testers is not improved, the obtained proofs are significantly simpler than the previous ones. We believe that our framework will help to understand the structure of efficiently testable properties. [ABSTRACT FROM AUTHOR]

In this paper, we formulate the optimal supervisory control problem (OSCP) under partial observation and propose an algorithm to design the optimal nonblocking supervisor (ONS). In addition, we introduce an extended net cost including the observation cost of the events which is taken into account for the cost of setting up a mechanism to sense the events and solve the OSCP with the extended net cost. [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]

In this paper, we look at the problem of spatially scaling color images. We focus on an approach that takes advantage of the human visual system's color spatial frequency sensitivity. The algorithm performs an efficient least-squares (LS) resolution conversion for the luminance channel and a low-complexity pixel replication/reduction in the chrominance channels. The performance of the algorithm is compared to a LS method in sRGB and CIELAB color spaces, as well as standard bilinear interpolation in sRGB space. The comparisons are made in terms of computational cost and color error in sCIELAB. [ABSTRACT FROM AUTHOR]

Abstract Recently, an online agglomerative clustering method called AddC (I. D. Guedalia et al . Neural Comput . {\bf 11} (1999), 521--540) was proposed for nonstationary data clustering. Although AddC possesses many good attributes, a vital problem of that method is its sensitivity to noises, which limits its use in real-word applications. In this paper, based on \hbox{kernel-induced} distance measures, a robust online clustering (ROC) algorithm is proposed to remedy the problem of AddC. Experimental results on artificial and benchmark data sets show that ROC has better clustering performances than AddC, while still inheriting advantages such as clustering data in a single pass and without knowing the exact number of clusters beforehand. [ABSTRACT FROM AUTHOR]

Without additional resources, it is often impossible to transform one entangled quantum state into another with local quantum operations and classical communication. Jonathan and Plenio (Phys. Rev. Left., vol. 83, p. 3566, 1999) presented an interesting example showing that the presence of another state, called a catalyst, enables such a transformation without changing the catalyst. They also pointed out that in general it is very hard to find an analytical condition under which a catalyst exists. In this paper, we study the existence of catalysts for two incomparable quantum states. For the simplest case of 2 × 2 catalysts for transformations from one 4 × 4 state to another, a necessary and sufficient condition for existence is found. For the general case, we give an efficient polynomial time algorithm to decide whether a k × k catalyst exists for two n × n incomparable states, where k is treated as a constant. [ABSTRACT FROM AUTHOR]

Abstract This paper provides an analysis of the behavior of separate-and-conquer or covering rule learning algorithms by visualizing their evaluation metrics and their dynamics in coverage space, a variant of ROC space. Our results show that most commonly used metrics, including accuracy, weighted relative accuracy, entropy, and Gini index, are equivalent to one of two fundamental prototypes: precision, which tries to optimize the area under the ROC curve for unknown costs, and a cost-weighted difference between covered positive and negative examples, which tries to find the optimal point under known or assumed costs. We also show that a straightforward generalization of the m-estimate trades off these two prototypes. Furthermore, our results show that stopping and filtering criteria like CN2s significance test focus on identifying significant deviations from random classification, which does not necessarily avoid overfitting. We also identify a problem with Foils MDL-based encoding length restriction, which proves to be largely equivalent to a variable threshold on the recall of the rule. In general, we interpret these results as evidence that, contrary to common conception, pre-pruning heuristics are not very well understood and deserve more investigation. [ABSTRACT FROM AUTHOR]

In this paper, we give a realization of crystal bases of the fundamental representations over Uq(Cn(1)) in terms of Young diagrams k introduced by Premat. Further, we give a generalized Lascoux–Leclerc–Thibon algorithm for computing the global bases. [ABSTRACT FROM AUTHOR]

In this paper, we give a realization of crystal bases of the fundamental representations over Uq(Cn(1)) in terms of Young diagrams k introduced by Premat. Further, we give a generalized Lascoux–Leclerc–Thibon algorithm for computing the global bases. [ABSTRACT FROM AUTHOR]

In this paper, we use the grey relational analysis to solve the clock routing with minimal clock skew in SoC. Experimental results show that our approach can reduce the clock skew up to I7.02%∼29.33% and 19.33%∼20.01% in average than that of MMM and GMA algorithms, respectively. The results demonstrate that our proposed method can achieve a good circuit performance in SoC. [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]