Search

Meshfree approximation schemes possess a high potential in computer aided engineering due to their large flexibility. Especially the tremendous progress in processor technology within recent years relativizes the increase in computation time due to the inherent search algorithm. Nevertheless meshfree approximation schemes are still faced with some challenges, like imposition of Dirichlet boundary conditions, robustness of the algorithm and accuracy. The recent developed Optimal Transportation Meshfree (OTM) method seemed to overcome most of these problems. In this paper the OTM solution scheme is combined with a standard search algorithm in order to allow a simple and flexible computation. However this scheme is not stable for some examples of application. Hence an investigation is conducted which shows that the reason for this instability is due to underintegration. Based on this investigation a remedy to stabilize the algorithm is suggested which is based on well known concepts to control the hourglass effects in the Finite Element Method. In contrast to the original publication, the OTM algorithm is derived here from the principle of virtual work. Local maximum entropy shape functions are used which possess a weak Kronecker- δ property. This enables a direct imposition of Dirichlet boundary conditions if the boundary is convex. The limitations of this basis function are also addressed in this paper. Additionally, the search algorithm presented fulfills basic topological requirements. Several examples are investigated demonstrating the improved behavior of the stabilized OTM algorithm. [ABSTRACT FROM AUTHOR]

Evolutionary multi-objective optimization (EMO) algorithms are actively used for answering optimization problems with multiple contradictory objectives and scheming interpretable and precise real-time applications. A majority of existing EMO algorithms performs better on two or three objectives non-dominated problems; however, they meet complications in managing and maintaining a set of optimal solutions to multi-objective optimization problems. This paper proposes a search space-based multi-objective evolutionary algorithm (SSMOEA) for multi-objective optimization problems. To accomplish the potential of the search space-based method for solving multi-objective optimization problems and to reinforce the selection procedure toward the ideal direction while sustaining an extensive and uniform distribution of solutions is our key objective. To the best of our knowledge, this paper is the first attempt to propose a search space-based multi-objective evolutionary algorithm for multi-objective optimization. The experimental setup used showed that the proposed algorithm is good and competitive in comparison to the existing EMO algorithms from the viewpoint of finding a scattered and estimated solution set in multi-objective optimization problems. SSMOEA can achieve a good trade-off between search space convergence and search space diversity in the appropriate experimental setup. [ABSTRACT FROM AUTHOR]

During the last decade, the paradigm of compressed sensing has gained significant importance in the signal processing community. While the original idea was to utilize sparsity assumptions to design powerful recovery algorithms of vectors x ∈ R d , the concept has been extended to cover many other types of problems. A noteable example is low-rank matrix recovery. Many methods used for recovery rely on solving convex programs. A particularly nice trait of compressed sensing is its geometrical intuition. In recent papers, a classical optimality condition has been used together with tools from convex geometry and probability theory to prove beautiful results concerning the recovery of signals from Gaussian measurements. In this paper, we aim to formulate a geometrical condition for stability and robustness, i.e. for the recovery of approximately structured signals from noisy measurements. We will investigate the connection between the new condition with the notion of restricted singular values , classical stability and robustness conditions in compressed sensing, and also to important geometrical concepts from complexity theory. We will also prove the maybe somewhat surprising fact that for many convex programs, exact recovery of a signal x 0 immediately implies some stability and robustness when recovering signals close to x 0 . [ABSTRACT FROM AUTHOR]

Abstract In this paper we show that it is possible to estimate the backward error for the approximation of the matrix exponential on-the-fly , without the need to precompute in high precision quantities related to specific accuracies. In this way, the scaling parameter s and the degree m of the truncated Taylor series (the underlying method) are adapted to the input matrix and not to a class of matrices sharing some spectral properties, such as with the classical backward error analysis. The result is a very flexible method which can approximate the matrix exponential at any desired accuracy. Moreover, the risk of overscaling, that is the possibility to select a value s larger than necessary, is mitigated by a new choice as the sum of two powers of two. Finally, several numerical experiments in MATLAB with data in double and variable precision and with different tolerances confirm that the method is accurate and often faster than available good alternatives. [ABSTRACT FROM AUTHOR]

Highlights • A framework for convexifying MINLP problems containing signomial functions and twice-differentiable functions is presented. • Lifting transformation schemes based on power, exponential and α BB-type reformulations is used. • The transformations used in the framework are obtained by solving an optimization problem in a preprocessing step. • The reformulations technique is included in a global algorithm that can solve any twice-differentiable MINLP problem. Abstract In this paper, a framework for reformulating nonconvex mixed-integer nonlinear programming (MINLP) problems containing twice-differentiable (C 2) functions to convex relaxed form is discussed. To provide flexibility and for utilizing more effective transformation strategies, the twice-differentiable functions can be partitioned into convex, signomial and general nonconvex functions. The latter two can then be convexified using lifting transformations in combination with approximations using piecewise linear functions (PLFs). However, since there are many degrees of freedom in how to select the set of transformations, an optimization-based method is proposed for finding an optimal set. The lifting transformations are based on single-variable power and exponential transformations for signomials. For nonconvex C 2-functions the α reformulation (α R) technique as well as more generally the method of difference of convex functions can be applied. In the α R, the α BB convex underestimator can be used. The framework is utilized in the α signomial global optimization (α SGO) algorithm to find the ϵ -global solution to a nonconvex problem by iteratively updating the approximations provided by the PLFs. The framework can also be used to directly obtain a convex relaxation of any nonconvex MINLP problem of the specified type to a determined accuracy. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of computing the 2-vertex-connected components of directed graphs. We present a new algorithm for solving this problem in O ( n m ) time. Furthermore, we show that the old algorithm of Erusalimskii and Svetlov runs in O ( n m 2 ) time. In this paper, we investigate the relationship between 2-vertex-connected components and dominator trees. We also consider three applications of our new algorithm, which are approximation algorithms for problems that are generalization of the problem of approximating the smallest 2-vertex-connected spanning subgraph of 2-vertex-connected directed graph. [ABSTRACT FROM AUTHOR]

Particle-based methods based on material models using spheres can provide good approximations for many physical phenomena at both the micro and macroscales. The point of departure for the simulations, in general, is a dense arrangement of spherical particles (sphere pack) inside a given container. For generic domains, the generation of a sphere pack may be complex and time-consuming, especially if the pack must comply with a prescribed sphere size distribution and the stability requirements of the simulation. The primary goal of this paper is to present an efficient algorithm that is capable of producing packs with millions of spheres following a statistical sphere size distribution inside complex arbitrary domains. This algorithm uses a new strategy to ensure that the sphere size distribution is preserved even when large particles are rejected in the growing process. The paper also presents numerical results that enable an evaluation of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper we present an efficient framework for the evaluation of subdivision schemes with polynomial reproduction property. For all interested rational parameters between 0 and 1 with the same denominator, their exact limit positions on the subdivision curve can be obtained by solving a system of linear equations. When the framework is applied to binary and ternary 4-point interpolatory subdivision schemes, we find that the corresponding coefficient matrices are strictly diagonally dominant, and so the evaluation processes are robust. For any individual irrational parameters between 0 and 1, its approximate value is computed by a recursive algorithm which can attain an arbitrary error bound. For surface schemes generalizing univariate subdivision schemes with polynomial reproduction property, exact evaluation methods can also be derived by combining Stam’s method with that of this paper. [ABSTRACT FROM AUTHOR]

Empirical evidence shows that repositories of business process models used in industrial practice contain significant amounts of duplication. This duplication arises for example when the repository covers multiple variants of the same processes or due to copy-pasting. Previous work has addressed the problem of efficiently retrieving exact clones that can be refactored into shared subprocess models. This paper studies the broader problem of approximate clone detection in process models. The paper proposes techniques for detecting clusters of approximate clones based on two well-known clustering algorithms: DBSCAN and Hierarchical Agglomerative Clustering (HAC). The paper also defines a measure of standardizability of an approximate clone cluster, meaning the potential benefit of replacing the approximate clones with a single standardized subprocess. Experiments show that both techniques, in conjunction with the proposed standardizability measure, accurately retrieve clusters of approximate clones that originate from copy-pasting followed by independent modifications to the copied fragments. Additional experiments show that both techniques produce clusters that match those produced by human subjects and that are perceived to be standardizable. [ABSTRACT FROM AUTHOR]

In this paper, we significantly extend the applicability of state-of-the-art ELDP (equations for linearizing discrete product terms) method by providing a new linearization to handle more complicated non-linear terms involving both of discrete and bounded continuous variables. A general class of “representable programming problems” is formally proposed for a much wider range of engineering applications. Moreover, by exploiting the logarithmic feature embedded in the discrete structure, we present an enhanced linear reformulation model which requires half an order fewer equations than the original ELDP. Computational experiments on various engineering design problems support the superior computational efficiency of the proposed linearization reformulation in solving engineering optimization problems with discrete and bounded continuous variables. [ABSTRACT FROM AUTHOR]

In this paper, we consider the matrix equation A X A H + C Y C H = F , where A , C and F are given matrices with appropriate sizes and [ X , Y ] is an unknown Hermitian and generalized skew-Hamiltonian matrix pair. Based on matrix differential calculus and projection theorem in inner product spaces, we exploit the best approximate solution [ X ̂ , Y ̂ ] in the set S to a given matrix pair [ X ∗ , Y ∗ ] , where S signifies the least-squares Hermitian and generalized skew-Hamiltonian solution set of the matrix equation A X A H + C Y C H = F . The analytical expression of the best approximate solution is presented by applying the canonical correlation decomposition and the generalized singular value decomposition. Finally, a numerical algorithm and an illustrated example are given. [ABSTRACT FROM AUTHOR]

This paper concerns a two-field reduced basis algorithm for the metamodelling of parametrized one-way coupled thermoelasticity problems based on the constitutive relation error (CRE) estimation. The coupled system consists of parametrized thermal diffusion and elastostatic equations which are explicitly coupled in a one-way manner. The former can be solved in advance independently and the latter can be solved afterwards using the solution of the former. For the fast and accurate analysis of the coupled system, we developed an algorithm that can choose adaptively the number of reduced basis functions of the temperature field to approximate the CRE equality of the mechanical field. We compute approximately the upper bound for the true errors of displacement and stress fields in energy norms. To enable this, a two-field greedy sampling strategy is adopted to construct the displacement and stress fields in an efficient manner. The computational efficiency of the proposed approach is demonstrated with computing the effective coefficient of thermal expansion of heterogeneous materials. [ABSTRACT FROM AUTHOR]

A string T of length m is periodic in P of length p if P is a substring of T and T [ i ] = T [ i + p ] for all 0 ≤ i ≤ m − p − 1 and m ≥ 2 p . The shortest such prefix, P , is called the period of T (i.e., P = T [ 0 . . p − 1 ] ). In this paper we investigate the period recovery problem. Given a string S of length n , find the primitive period(s) P such that the distance between S and a string T that is periodic in P is below a threshold τ . We consider the period recovery problem over both the Hamming distance and the edit distance. For the Hamming distance case, we present an O ( n log ⁡ n ) -time algorithm, where τ is given as ⌊ n ( 2 + ϵ ) p ⌋ , for ϵ > 0 . For the edit distance case, τ = ⌊ n ( 3.75 + ϵ ) p ⌋ and ϵ > 0 , we provide an O ( n 4 / 3 ) -time algorithm. [ABSTRACT FROM AUTHOR]

An exact run in a string T is a non-empty substring of T that is a repetition of a smaller substring possibly followed by a prefix of it. Finding maximal exact runs in strings is an important problem and therefore a well-studied one in the area of stringology. For a given string T of length n , finding all maximal exact runs in the string can be done in O ( n log ⁡ n ) time on general ordered alphabets or O ( n ) time on integer alphabets. In this paper, we investigate the maximal approximate runs problem: for a given string T and a number k , find non-empty substrings T ′ of T such that changing at most k letters in T ′ transforms them into a maximal exact run. We present an O ( n k 2 log 2 ⁡ k + o c c ) algorithm to solve this problem, where occ is the number of substrings found. [ABSTRACT FROM AUTHOR]

The Hasofer–Lind and Rackwitz–Fiessler (HL-RF) method is a popular iterative approximation method in structural reliability analysis. However, it may pose numerical instability and result in divergence in the face of high nonlinearity. In the present paper, two adjusting parameters are included in this method and a generalization of HL-RF is proposed. The represented parameters are to control the convergence of the sequence especially when nonlinearity increases. The proposed algorithm actually improves the performance of HL-RF in convergence, while it remains as simple as HL-RF to implement without any need to merit functions or line search processes, needed in many approximation methods. Through various numerical examples, the robustness and efficiency of the proposed algorithm in highly nonlinear cases have been shown. [ABSTRACT FROM AUTHOR]

The algorithm by Al-Mohy and Higham (2011) [2] computes an approximation to e A b for given A and b , where A is an n -by- n matrix and b is, for example, a vector of dimension n . It uses a scaling together with a truncated Taylor series approximation to the exponential of the scaled matrix. In this paper, a method is developed for estimating the roundoff error of the computed solution. An asymptotic expansion of this error for small values of the unit roundoff is the basis of the method. The roundoff error is further expressed in terms of sums of rounding errors, which occur during the computation. A second approximation to e A b , which is computed with a lower precision than the first one, is used to evaluate these rounding errors in practice. The result is an upper bound on the normwise relative roundoff error. Further, an algorithm is proposed for computing the error bound. The cost for performing this algorithm depends on the type of problem and the accuracy, which is required for the error estimate. In case that all computations are performed with standard precisions, this cost can be expressed in terms of the number of computed matrix-vector products and is bounded from above by two times the cost for computing e A b . [ABSTRACT FROM AUTHOR]

Data is growing at an exponential pace. To cope with this data explosion, we need effective data processing and analysis techniques. Feature selection is selecting a subset of features from a dataset that still provides most of the useful information. Various tools are available as underlying framework for this process however, Rough Set Theory is the most prominent tool due to its analysis friendly nature. Majority of Rough Set based feature selection algorithms use positive region based dependency measure as the sole criteria to select feature subset. Calculating positive region requires calculation of lower approximation which consequently involves indiscernibility relation. In this paper, new definitions of two Rough Set preliminaries i.e. lower and upper rough set approximation are proposed. New definitions of approximations are computationally less expensive as compared to the conventional. The proposed redefinitions showed 42.78% decrease in execution time for redefined lower approximation and 43.06% decrease in case of redefined upper approximation, for five publicly available datasets while maintaining 100% accuracy. Finally based on these redefined approximations we proposed a feature selection algorithm, which when compared with state of the art techniques showed significant increase in performance without the affecting the accuracy. [ABSTRACT FROM AUTHOR]

Sweep coverage provides solutions for the applications in wireless sensor networks, where periodic monitoring is sufficient instead of continuous monitoring. The objective of the sweep coverage problem is to minimize the number of sensors required in order to guarantee sweep coverage for a given set of points of interest on a plane. Instead of using only mobile sensors for sweep coverage, use of both static and mobile sensors can be more effective in terms of energy utilization. In this paper, we introduce two variations in sweep coverage problem, where energy consumption by the sensors is taken into consideration. First, an energy efficient sweep coverage problem is proposed, where the objective is to minimize energy consumption by a set of sensors (mobile and/or static) with guaranteed sweep coverage. We prove that the problem is NP-hard and cannot be approximated within a factor of 2. An 8-approximation algorithm is proposed to solve the problem. A 2-approximation algorithm is also proposed for a special case. Second, an energy restricted sweep coverage problem is proposed, where the objective is to find the minimum number of mobile sensors to guarantee sweep coverage subject to the condition that the energy consumption by a mobile sensor in a given time period is bounded. We propose a ( 5 + 2 α ) -approximation algorithm to solve this NP-hard problem. [ABSTRACT FROM AUTHOR]

Systems of reaction–diffusion equations are commonly used in biological models of food chains. The populations and their complicated interactions present numerous challenges in theory and in numerical approximation. In particular, self-diffusion is a nonlinear term that models overcrowding of a particular species. The nonlinearity complicates attempts to construct efficient and accurate numerical approximations of the underlying systems of equations. In this paper, a new nonlinear splitting algorithm is designed for a partial differential equation that incorporates self-diffusion. We present a general model that incorporates self-diffusion and develop a numerical approximation. The numerical analysis of the approximation provides criteria for stability and convergence. Numerical examples are used to illustrate the theoretical results. [ABSTRACT FROM AUTHOR]

An edge-bicolored graph G = ( V , R ∪ B ) is called Red/Blue-split graph if there exists a partition I B and I R of V such that I B and I R are independent sets in ( V , B ) and ( V , R ) , respectively. Red/Blue-split graphs generalize several well studied graph classes including split graphs, bipartite graphs and König–Egerváry graphs. In this paper we consider the algorithmic complexity of various optimization problems like minimum edge (or vertex) deletion and maximum edge (or vertex) induced subgraph related to Red/Blue split graphs. All these problems are NP -hard and thus we look at them from algorithmic paradigms that are meant for coping with NP -hardness. We obtain various hardness as well as algorithmic results for these problems in the realm of approximation algorithms and parameterized complexity. The main tool we use to obtain all our results is polynomial time transformations between appropriate problems. On the way, we also resolve some problems related to inapproximability about certain optimization problems mentioned by Korach et al. (2006) [17] . [ABSTRACT FROM AUTHOR]

Abstract: In some recent papers, some procedures based on some weighted empirical measures related to decreasing-step Euler schemes have been investigated to approximate the stationary regime of a diffusion (possibly with jumps) for a class of functionals of the process. This method is efficient but needs the computation of the function at each step. To reduce the complexity of the procedure (especially for functionals), we propose in this paper to study a new scheme, called the mixed-step scheme, where we only keep some regularly time-spaced values of the Euler scheme. Our main result is that, when the coefficients of the diffusion are smooth enough, this alternative does not change the order of the rate of convergence of the procedure. We also investigate a Richardson–Romberg method to speed up the convergence and show that the variance of the original algorithm can be preserved under a uniqueness assumption for the invariant distribution of the “duplicated” diffusion, condition which is extensively discussed in the paper. Finally, we conclude by giving sufficient “asymptotic confluence” conditions for the existence of a smooth solution to a discrete version of the associated Poisson equation, condition which is required to ensure the rate of convergence results. [Copyright &y& Elsevier]

Highlights: [•] Aiming at the problem that how to classify T-splines this paper gives a mathematical analysis, and a sufficient condition of standard T-splines is also given. [•] Then this paper presents an algorithm of determining the T-spline classification, and we can get the inherently mathematical properties of T-splines by the algorithm. [ABSTRACT FROM AUTHOR]

Abstract: Although the rough set and intuitionistic fuzzy set both capture the same notion, imprecision, studies on the combination of these two theories are rare. Rule extraction is an important task in a type of decision systems where condition attributes are taken as intuitionistic fuzzy values and those of decision attribute are crisp ones. To address this issue, this paper makes a contribution of the following aspects. First, a ranking method is introduced to construct the neighborhood of every object that is determined by intuitionistic fuzzy values of condition attributes. Moreover, an original notion, dominance intuitionistic fuzzy decision tables (DIFDT), is proposed in this paper. Second, a lower/upper approximation set of an object and crisp classes that are confirmed by decision attributes is ascertained by comparing the relation between them. Third, making use of the discernibility matrix and discernibility function, a lower and upper approximation reduction and rule extraction algorithm is devised to acquire knowledge from existing dominance intuitionistic fuzzy decision tables. Finally, the presented model and algorithms are applied to audit risk judgment on information system security auditing risk judgement for CISA, candidate global supplier selection in a manufacturing company, and cars classification. [Copyright &y& Elsevier]

Abstract: This paper reports on improvements to recent work on the computation of a structured low rank approximation of the Sylvester resultant matrix of two inexact polynomials and . Specifically, it has been shown in previous work that these polynomials must be processed before a structured low rank approximation of is computed. The existing algorithm may still, however, yield a structured low rank approximation of , but not a structured low rank approximation of , which is unsatisfactory. Moreover, a structured low rank approximation of must be equal to, apart from permutations of its columns, a structured low rank approximation of , but the existing algorithm does not guarantee the satisfaction of this condition. This paper addresses these issues by modifying the existing algorithm, such that these deficiencies are overcome. Examples that illustrate these improvements are shown. [Copyright &y& Elsevier]

Many particulate processes in process and bioprocess engineering can be described with multi-dimensional population balances. Approximate moment methods are frequently used for their solution. In the present paper a new approach is presented, which is particular efficient when the number of internal coordinates is high. It combines the direct quadrature method of moments with monomial cubatures. With the new method the computational effort increases only polynomially, in the simplest case even only linearly with the number of internal coordinates, compared to an exponential increase for the well known Gausssian cubatures. The technique is evaluated for a five dimensional benchmark problem describing virus replication in continuous cell cultures. Furthermore, the algorithm is applied to analyze influenza virus replication in genetically modified cell lines. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we develop the adaptive data fitting algorithms by virtue of the local property of the Progressive-iterative approximation (abbr. PIA), which generates the fitting curve (patch) by adjusting the control points of a blending curve (patch) iteratively. In the adaptive data fitting algorithms, the control points are classified into two classes, namely, active and fixed control points, and only the active control points need to be adjusted in each iteration, thus saving computation greatly. Lots of examples and experimental data are presented to demonstrate the efficiency of the adaptive data fitting algorithm. Since the PIA method can be made parallel easily, the adaptive data fitting algorithm developed in this paper has important applications in parallel large scale data fitting. [Copyright &y& Elsevier]

In this paper, we propose a new highly efficient two-step algorithm based on local Gauss integration for the 2D steady-state natural convection problem. The basic idea of the algorithm is to compute an initial approximation for the velocity, pressure and temperature based on a lowest equal-order finite element pair P 1 – P 1 – P 1 , then to solve a linear system based on a quadratic equal-order finite element pair P 2 – P 2 – P 2 on the same mesh. Next, we give the corresponding stability and convergence of the algorithm, which show that the new two-step algorithm has the same order convergence rate as the quadratic equal-order stabilized finite element method. Finally, some numerical examples show that the new method is efficient, reliable, has good precision and can save a lot of computational time compared with the quadratic equal-order stabilized method. [ABSTRACT FROM AUTHOR]

Abstract: The linear complementarity problem is to find a vector in satisfying , ,, where and are given. In this paper, we use the fact that solving is equivalent to solving the nonlinear equation where is a function from into itself defined by . We build a sequence of smooth functions which is uniformly convergent to the function . We show that, an approximation of the solution of the (when it exists) is obtained by solving for a parameter large enough. Then we give a globally convergent hybrid algorithm which is based on vector divisions and the secant method for solving . We close our paper with some numerical simulations to illustrate our theoretical results, and to show that this method can solve efficiently large-scale linear complementarity problems. [Copyright &y& Elsevier]

Abstract: Many simulation algorithms (chemical reaction systems, differential systems arising from the modelling of transient behaviour in the process industries etc.) contain the numerical solution of systems of differential equations. For the efficient solution of the above mentioned problems, linear multistep methods or Runge–Kutta single-step methods are used. For the simulation of chemical procedures the radial Schrödinger equation is used frequently. In the present paper we will study a class of linear multistep methods. More specifically, the purpose of this paper is to develop an efficient algorithm for the approximate solution of the radial Schrödinger equation and related problems. This algorithm belongs in the category of the multistep methods. In order to produce an efficient multistep method the phase-lag property and its derivatives are used. Hence the main result of this paper is the development of an efficient multistep method for the numerical solution of systems of ordinary differential equations with oscillating or periodical solutions. The reason of their efficiency, as the analysis proved, is that the phase-lag and its derivatives are eliminated. Another reason of the efficiency of the new obtained methods is that they have high algebraic order [Copyright &y& Elsevier]

Abstract: In this paper, we proposed an algorithm for solving the linear systems of matrix equations over the generalized -reflexive matrix (). According to the algorithm, the solvability of the problem can be determined automatically. When the problem is consistent over the generalized -reflexive matrix , for any generalized -reflexive initial iterative matrices , the generalized -reflexive solution can be obtained within finite iterative steps in the absence of roundoff errors. The unique least-norm generalized -reflexive solution can also be derived when the appropriate initial iterative matrices are chosen. A sufficient and necessary condition for which the linear systems of matrix equations is inconsistent is given. Furthermore, the optimal approximate solution for a group of given matrices can be derived by finding the least-norm generalized -reflexive solution of a new corresponding linear system of matrix equations. Finally, we present a numerical example to verify the theoretical results of this paper. [Copyright &y& Elsevier]

Abstract: In this paper, the factor of safety for a prescribed slip surface will be determined from an equivalent lower bound method (extremum principle), which can satisfy all equilibrium conditions without an interslice force function. This approach will give an overall factor of safety close to that from the classical methods for normal problems, while the thrust line, the local factor of safety for individual slice/block and the progressive yielding phenomenon can be estimated, which will be useful for some special cases. The force and moment equilibrium of every slice will be satisfied, while the location of the thrust line will always be acceptable in the present formulation. To solve the difficult optimisation problem, an innovative coupled particle swarm/harmony search algorithm is proposed in this paper, and a practical engineering problem for which the factor of safety is close to 1.0 is used to illustrate the consideration of the residual strength in the limit equilibrium slope stability analysis. [Copyright &y& Elsevier]

Abstract: In this paper, we study the following minimization problem where is a bounded linear operator, is some constant, is a potential function for , is the set of fixed points of nonexpansive mapping and is the solution set of an equilibrium problem. This paper introduces two new algorithms (one implicit and one explicit) that can be used to find the solution of the above minimization problem. [Copyright &y& Elsevier]

Abstract: Rough k-means clustering describes uncertainty by assigning some objects to more than one cluster. Rough cluster quality index based on decision theory is applicable to the evaluation of rough clustering. In this paper we analyze rough k-means clustering with respect to the selection of the threshold, the value of risk for assigning an object and uncertainty of objects. According to the analysis, clusters presented as interval sets with lower and upper approximations in rough k-means clustering are not adequate to describe clusters. This paper proposes an interval set clustering based on decision theory. Lower and upper approximations in the proposed algorithm are hierarchical and constructed as outer-level approximations and inner-level ones. Uncertainty of objects in out-level upper approximation is described by the assignment of objects among different clusters. Accordingly, ambiguity of objects in inner-level upper approximation is represented by local uniform factors of objects. In addition, interval set clustering can be improved to obtain a satisfactory clustering result with the optimal number of clusters, as well as optimal values of parameters, by taking advantage of the usefulness of rough cluster quality index in the evaluation of clustering. The experimental results on synthetic and standard data demonstrate how to construct clusters with satisfactory lower and upper approximations in the proposed algorithm. The experiments with a promotional campaign for the retail data illustrates the usefulness of interval set clustering for improving rough k-means clustering results. [ABSTRACT FROM AUTHOR]

Abstract: This paper describes our methodology for building conformant planners, which is based on recent advances in the theory of action and change and answer set programming. The development of a planner for a given dynamic domain starts with encoding the knowledge about fluents and actions of the domain as an action theory of some action language. Our choice in this paper is – an action language with dynamic and static causal laws and executability conditions. An action theory of defines a transition diagram containing all the possible trajectories of the domain. A transition belongs to iff the execution of the action a in the state s may move the domain to the state . The second step in the planner development consists in finding a deterministic transition diagram such that nodes of are partial states of , its arcs are labeled by actions, and a path in from an initial partial state to a partial state satisfying the goal corresponds to a conformant plan for and in . The transition diagram is called an ‘approximation’ of . We claim that a concise description of an approximation of can often be given by a logic program under the answer sets semantics. Moreover, complex initial situations and constraints on plans can be also expressed by logic programming rules and included in . If this is possible then the problem of finding a parallel or sequential conformant plan can be reduced to computing answer sets of . This can be done by general purpose answer set solvers. If plans are sequential and long then this method can be too time consuming. In this case, is used as a specification for a procedural graph searching conformant planning algorithm. The paper illustrates this methodology by building several conformant planners which work for domains with complex relationship between the fluents. The efficiency of the planners is experimentally evaluated on a number of new and old benchmarks. In addition we show that for a subclass of action theories of our planners are complete, i.e., if in we cannot get from to a state satisfying the goal then there is no conformant plan for and in . [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of clustering a set of n finite point-sets in d-dimensional Euclidean space. Different from the traditional clustering problem (called points clustering problem where the to-be-clustered objects are points), the point-sets clustering problem requires that all points in a single point-set be clustered into the same cluster. This requirement disturbs the metric property of the underlying distance function among point-sets and complicates the clustering problem dramatically. In this paper, we use a number of interesting observations and techniques to overcome this difficulty. For the k-center clustering problem on point-sets, we give an -time 3-approximation algorithm and an -time -approximation algorithm, where m is the total number of input points and k is the number of clusters. When k is a small constant, the performance ratio of our algorithm reduces to for any . For the k-median problem on point-sets, we present a polynomial time -approximation algorithm. Our approaches are rather general and can be easily implemented for practical purpose. [Copyright &y& Elsevier]

Abstract: In this paper we introduce an algorithm for the creation of polyhedral approximations for certain kinds of digital objects in a three-dimensional space. The objects are sets of voxels represented as strongly connected subsets of an abstract cell complex. The proposed algorithm generates the convex hull of a given object and modifies the hull afterwards by recursive repetitions of generating convex hulls of subsets of the given voxel set or subsets of the background voxels. The result of this method is a polyhedron which separates object voxels from background voxels. The objects processed by this algorithm and also the background voxel components inside the convex hull of the objects are restricted to have genus 0. The second aim of this paper is to present some practical improvements to the discussed convex hull algorithm to reduce computation time. [Copyright &y& Elsevier]

Abstract: In this paper, we consider a restricted variant of the scheduling problem, where the machines are the strategic players. For this multi-parameter mechanism design problem, the only known truthful mechanisms use task independent allocation algorithms and only have approximation ratio [N. Nisan, A. Ronen. Algorithmic mechanism design (extended abstract), in: STOC’99: Proceedings of the thirty-first annual ACM symposium on Theory of computing, ACM, New York, NY, USA, 1999. pp. 129–140; A. Mu’alem, M. Schapira, Setting lower bounds on truthfulness: Extended abstract, in: SODA’07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2007, pp. 1143–1152; P. Lu, C. Yu, An improved randomized truthful mechanism for scheduling unrelated machines, in: 25th International Symposium on Theoretical Aspects of Computer Science, STACS, 2008, pp. 527–538; P. Lu, C. Yu, Randomized truthful mechanisms for scheduling unrelated machines, in: C.H. Papadimitriou, S. Zhang (Eds.), Proceedings of WINE, in: Lecture Notes in Computer Science, vol. 5385, Springer, 2008, pp. 402–413]. Lavi and Swamy first use the cycle monotone condition and design a 3-approximation truthful mechanism for a two value variant in [R. Lavi, C. Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, in: EC’07: Proceedings of the 8th ACM conference on Electronic commerce, ACM, New York, NY, USA, 2007, pp. 252–261], where the processing time of task on machine , say , can only be either a lower value or a higher value . We consider a generalized variant, where lies in and is a parameter satisfying some condition. We consider two special cases, case A when , and case B when ,, and give randomized truthful mechanisms with approximation ratio for both cases. Based on these two cases’ results, we are also able to deal with the general case of our two-range-values scheduling problem. We use a combination of two mechanisms, which is also a novel method in mechanism design for scheduling problems, and finally we give a randomized truthful mechanism with approximation ratio . Although the generalization seems a little incremental, we actually use a very novel technique in the key step of proving truthfulness for case A, as well as a new mechanism scheme for case B. Besides, the results in this paper are the first truthful mechanisms with constant approximation ratios when a machine (player) can report infinitely possible values, which is quite different from the two value variant, in which only finite values are available. Furthermore, together with Lavi and Swamy’s work, our results suggest that such a task-dependent approach can really do much better for the scheduling unrelated machines problem. [Copyright &y& Elsevier]

Abstract: Objective: This paper presents an algorithm for the solution of the motif discovery problem (MDP). Methods and materials: Motif discovery problem can be considered in two cases: motifs with insertions/deletions, and motifs without insertions/deletions. The first group motifs can be found by stochastic and approximated methods. The second group can be found by using stochastic and approximated methods, but also deterministic method. We proved that the second group motifs can be found with a deterministic algorithm, and so, it can be said that the second motifs finding is a P-type problem as proved in this paper. Results and conclusions: An algorithm was proposed in this paper for motif discovery problem. The proposed algorithm finds all motifs which are occurred in the sequence at least two times, and it also finds motifs of various sizes. Due to this case, this algorithm is regarded as Automatic Exact Motif Discovery Algorithm. All motifs of different sizes can be found with this algorithm, and this case was proven in this paper. It shown that automatic exact motif discovery is a P-type problem in this paper. The application of the proposed algorithm has been shown that this algorithm is superior to MEME, MEME3, Motif Sampler, WEEDER, CONSENSUS, AlignACE. [Copyright &y& Elsevier]

Abstract: This paper explores a new family of 2D interpolating subdivision schemes that calculate subdivision points from tangent specifications. In this approach each level of subdivision drives the curve toward its specified tangents. The paper describes the underlying algorithmic formulation, and outlines a number of variations, which differ in how subdivision points are computed from tangents or in how tangents are derived. The different characteristics of these variations are shown to provide an interesting range of shapes, giving a high degree of artistic control. Each variation is shown to guarantee C1 continuity except for special identifiable cases, and some of these variations can produce circles. A number of examples are explored that demonstrate the power of the approach as a modeling tool for constructing complex curves, and a comparison is made with curves produced by the Kobbelt subdivision scheme. [Copyright &y& Elsevier]

Given a simple polygon of vertices, the watchman route problem asks for a shortest (closed) route inside such that each point in the interior of can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most two times that of the shortest watchman route. The best known algorithm for computing a shortest watchman route takes time, which is too complicated to be suitable in practice. This paper also involves an optimal time algorithm for computing the set of so-called essential cuts, which are the line segments inside the polygon such that any route visiting them is a watchman route. It solves an intriguing open problem by improving the previous time result, and is thus of interest in its own right. [Copyright &y& Elsevier]

In this paper, we consider a variant of the well-known Steiner tree problem. Given a complete graph with a cost function and two subsets and satisfying , a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in such that each vertex in cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we present a-approximation algorithm for the problem, where is the best-known approximation ratio for the Steiner tree problem. [Copyright &y& Elsevier]

Abstract: In this paper, we concern ourselves with the determination and evaluation of polynomials that are orthogonal with respect to a general discrete Sobolev inner product, that is, an ordinary inner product on the real line plus a finite sum of atomic inner products involving a finite number of derivatives. In a previous paper we provided a complete set of formulas to compute the coefficients of this recurrence. Here, we study the numerical stability of these algorithms for the generation and evaluation of a finite series of Sobolev orthogonal polynomials. Besides, we propose several techniques for reducing and controlling the rounding errors via theoretical running error bounds and a carefully chosen recurrence. [Copyright &y& Elsevier]