Search

Abstract: In this paper, we propose a reweighted nuclear norm minimization algorithm based on the weighted fixed point method (RNNM–WFP algorithm) to recover a low rank matrix, which iteratively solves an unconstrained minimization problem introduced as a nonconvex smooth approximation of the low rank matrix minimization problem. We prove that any accumulation point of the sequence generated by the RNNM–WFP algorithm is a stationary point of the minimization problem. Numerical experiments on randomly generated matrix completion problems indicate that the proposed algorithm has better recoverability compared to existing iteratively reweighted algorithms. [Copyright &y& Elsevier]

Abstract: This paper presents an extended minimal degree optimal Hankel norm approximation (MDOHNA) based order reduction algorithm using a basis-free descriptor which circumvents the requirement of computing balanced realized model for order reduction. Conjunction of system decomposition algorithm (Singh and Nagar, 2004) [21], (Kumar et al., 2012) [30,31] with MDOHNA is used as extension for order reduction of unstable systems. The developed algorithm is applicable for stable/unstable, linear time invariant, minimal/non-minimal, continuous/discrete-time systems as well. Further, effectiveness of the algorithm over existing techniques is validated with the help of a numerical example. [Copyright &y& Elsevier]

Abstract: A new method for fast evaluation of thin plate splines in two dimensions is presented. The paper first develops exponential approximations to thin plate splines. These are the analytical basis for an improved fast multipole evaluator. Analytic error bounds are supplemented by offline parallel numerical computation of the underlying error constants. These error constants enable adaptive selection of series lengths as a function of the weights associated with a source panel, and the desired accuracy. Numerical comparisons with a competing algorithm show that the new method is significantly faster when moderate to high precision is required. [Copyright &y& Elsevier]

Abstract: Given a set of non-parallel lines in the plane, a watchman route (tour) for is a closed curve contained in the union of the lines in such that every line is visited (intersected) by the route; we similarly define a watchman route (tour) for a connected set of line segments. The watchman route problem for a given set of lines or line segments is to find a shortest watchman route for the input set, and these problems are natural special cases of the watchman route problem in a polygon with holes (a polygonal domain). In this paper, we show that the problem of computing a shortest watchman route for a set of n non-parallel lines in the plane is polynomially tractable, while it becomes NP-hard in 3D. We give an alternative NP-hardness proof of this problem for line segments in the plane and obtain a polynomial-time approximation algorithm with ratio . Additionally, we consider some special cases of the watchman route problem on line segments, for which we provide exact algorithms or improved approximations. [Copyright &y& Elsevier]

Abstract: We address a linear fractional differential equation and develop effective solution methods using algorithms for the inversion of triangular Toeplitz matrices and the recently proposed QTT format. The inverses of such matrices can be computed by the divide and conquer and modified Bini’s algorithms, for which we present the versions with the QTT approximation. We also present an efficient formula for the shift of vectors given in QTT format, which is used in the divide and conquer algorithm. As a result, we reduce the complexity of inversion from the fast Fourier level to the speed of superfast Fourier transform, i.e., . The results of the paper are illustrated by numerical examples. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of computing a minimum bending energy path (or MinBEP) in a simple corridor. Given a simple 2D corridor C bounded by straight line segments and arcs of radius 2r, the MinBEP problem is to compute a path P inside C and crossing two pre-specified points s and t located at each end of C so that the bending energy of P is minimized. For this problem, we first show how to lower bound the bending energy of an optimal curve with bounded curvature, and then use this lower bound to design a -approximation algorithm for this restricted version of the MinBEP problem. Our algorithm is based on a number of interesting geometric observations and approximation techniques on smooth curves, and can be easily implemented for practical purpose. It is the first algorithm with a guaranteed performance ratio for the MinBEP problem. [Copyright &y& Elsevier]

Abstract: The K-means algorithm has good ability to handle the large number of scanned data. It is best suited for creation a desired shape curve-likes shape for near-best approximation of the scanned data point set. It presented an approximate set of scanned data points with a simple curves or surfaces. In this paper, the reverse engineering use for scanning the spur gear using 3D laser scanner and data is stored in point cloud format. Using this scanned data, reconstructing the smooth curve is achieved by proposed algorithm in MATLAB environment. In this study, scanned geometry and curve reconstruction technique suggested and it has been demonstrated to tooth curve reconstruction of spur gear as a complex surface object. Result of methodology is helpful to recreate the 3D CAD model of scanned object, which can be improve in work efficiency and reduce the product development cycle time with the application of CAD/CAE/CAM tools. [Copyright &y& Elsevier]

Abstract: Standard model order reduction techniques attempt to build reduced order models of large scale systems with similar input–output behavior over a wide range of input frequencies as the full system models. The method known as the dominant pole algorithm has previously been successfully used in combination with model order reduction techniques to approximate standard linear time-invariant dynamical systems and second order dynamical systems as well as nonlinear time-delay systems. In this paper, we show that the dominant pole algorithm can be adapted for parametric systems where these parameters usually have physical meaning. There are two approaches for finding dominant poles. These algorithms are illustrated by the second order numerical examples. [Copyright &y& Elsevier]

Abstract: In computational cognitive science, many cognitive processes seem to be successfully modeled as Bayesian computations. Yet, many such Bayesian computations have been proven to be computationally intractable (NP-hard) for unconstrained input domains, even if only an approximate solution is sought. This computational complexity result seems to be in strong contrast with the ease and speed with which humans can typically make the inferences that are modeled by Bayesian models. This contrast—between theory and practice—poses a considerable theoretical challenge for computational cognitive modelers: How can intractable Bayesian computations be transformed into computationally plausible ‘approximate’ models of human cognition? In this paper, three candidate notions of ‘approximation’ are discussed, each of which has been suggested in the cognitive science literature. We will sketch how (parameterized) computational complexity analyses can yield model variants that are tractable and which can serve as the basis of computationally plausible models of cognition. [Copyright &y& Elsevier]

Abstract: The concept of matching dependencies (mds) has recently been proposed for specifying matching rules for object identification. Similar to the functional dependencies (with conditions), mds can also be applied to various data quality applications such as detecting the violations of integrity constraints. In this paper, we study the problem of discovering similarity constraints for matching dependencies from a given database instance. First, we introduce the measures, support and confidence, for evaluating the utility of mds in the given data. Then, we study the discovery of mds with certain utility requirements of support and confidence. Exact algorithms are developed, together with pruning strategies to improve the time performance. Since the exact algorithm has to traverse all the data during the computation, we propose an approximate solution which only uses part of the data. A bound of relative errors introduced by the approximation is also developed. Finally, our experimental evaluation demonstrates the efficiency of the proposed methods. [Copyright &y& Elsevier]

Abstract: This paper introduces new and significantly fast algorithms to evaluate the price of double barrier options using binomial trees. To compute the price of double barrier options accurately, trees with large numbers of steps must be used, which is time consuming. In order to overcome this weakness, we develop new computational algorithms based on the spectral expansion method. The original idea of this method is coming from the eigenexpansion approach in PDEs. We show that this method enables us to compute double barrier options within 0.07 s, even if we use binomial trees with one billion steps. Moreover, this algorithm is easy to implement. In addition, the prices obtained by the proposed approach are always the same as those obtained by conventional binomial trees and show a good approximation to those by earlier studies. [Copyright &y& Elsevier]

Abstract: A semi-linear elliptic problem with variable coefficient is approximated by expanded mixed formulation based on the RTN and BDM mixed finite elements. In order to solve the nonlinear approximation system of equations efficiently, a two-grid algorithm is considered and discussed in this paper. The work includes a small nonlinear system on a coarse grid space with mesh size and a linear system on a fine grid space with mesh size . It follows from error estimates that asymptotically optimal accuracy can be obtained as long as the mesh sizes satisfy in the norm. Some numerical examples are presented to illustrate the theoretical results. [Copyright &y& Elsevier]

Abstract: In this paper, the differential geometry of the novel hierarchical Tucker format for tensors is derived. The set of tensors with fixed tree T and hierarchical rank is shown to be a smooth quotient manifold, namely the set of orbits of a Lie group action corresponding to the non-unique basis representation of these hierarchical tensors. Explicit characterizations of the quotient manifold, its tangent space and the tangent space of are derived, suitable for high-dimensional problems. The usefulness of a complete geometric description is demonstrated by two typical applications. First, new convergence results for the nonlinear Gauss–Seidel method on are given. Notably and in contrast to earlier works on this subject, the task of minimizing the Rayleigh quotient is also addressed. Second, evolution equations for dynamic tensor approximation are formulated in terms of an explicit projection operator onto the tangent space of . In addition, a numerical comparison is made between this dynamical approach and the standard one based on truncated singular value decompositions. [Copyright &y& Elsevier]

Curves are widely used in computer science to describe real-life objects such as slender deformable structures. Using only 3 parameters per element, piecewise helices offer an interesting and compact way of representing digital curves. In this paper, we present a robust and fast algorithm to approximate Bézier curves with piecewise helices. Our approximation algorithm takes a Bézier spline as input along with an integer N and returns a piecewise helix with N elements that closely approximates the input curve. The key idea of our method is to take evenly distributed points along the curve, together with their tangents, and interpolate these tangents with helices by slightly relaxing the points. Building on previous work, we generalize the proof for Ghoshʼs co-helicity condition, which serves us to guarantee the correctness of our algorithm in the general case. Finally, we demonstrate both the efficiency and robustness of our method by successfully applying it to various datasets of increasing complexity, ranging from synthetic curves created by an artist to automatic image-based reconstructions of real data such as hair, heart muscular fibers or magnetic field lines of a star. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, a new hybrid method based on fuzzy neural network for approximate solution of fully fuzzy matrix equations of the form , where A and D are two fuzzy number matrices and the unknown matrix X is a fuzzy number matrix, is presented. Then, we propose some definitions which are fuzzy zero number, fuzzy one number and fuzzy identity matrix. Based on these definitions, direct computation of fuzzy inverse matrix is done using fuzzy matrix equations and fuzzy neural network. It is noted that the uniqueness of the calculated fuzzy inverse matrix is not guaranteed. Here a neural network is considered as a part of a large field called neural computing or soft computing. Moreover, in order to find the approximate solution of fuzzy matrix equations that supposedly has a unique fuzzy solution, a simple algorithm from the cost function of the fuzzy neural network is proposed. To illustrate the easy application of the proposed method, numerical examples are given and the obtained results are discussed. [Copyright &y& Elsevier]

Abstract: To reduce contour error in contour-following tasks, a common approach is to design a controller based on the contour error information. Hence, real-time contouring error estimation plays an important role in contour-following control. However, the available second-order estimation formulas only apply to biaxial motion systems, and cannot be generalized to handle arbitrary contours tracked by multi-axis motion systems. In this paper, a point-to-curve distance function is defined, and its properties are investigated, especially, its second-order Taylor approximant is derived. On this basis, a novel second-order approach for calculating contour errors of arbitrary contours in real time is proposed. The inter-correlations between the present approach and four commonly used ones are classified. Simulation and experimental results demonstrate the effectiveness of the proposed contour error estimation algorithm. [Copyright &y& Elsevier]

Abstract: One of the most relevant topics in the analysis of biological networks is the identification of functional motifs inside a network. A recent approach introduced in literature, called Graph Motif, represents the network as a vertex-colored graph, and the motif as a multiset of colors. An occurrence of a motif in a vertex-colored graph is a connected induced subgraph of whose vertex set is colored exactly as . In this paper we investigate three different variants of the Graph Motif problem. The first two variants, Minimum Adding Motif (Min-Add Graph Motif) and Minimum Substitution Motif (Min-Sub Graph Motif), deal with approximate occurrences of a motif in the graph, while the third variant, Constrained Graph Motif (CGM), constrains the motif to contain a given set of vertices. We investigate the computational and parameterized complexity of the three problems. We show that Min-Add Graph Motifand Min-Sub Graph Motifare both NP-hard, even when is a set, and the graph is a tree with maximum degree in which each color appears at most twice. Then, we show that Min-Sub Graph Motifis fixed-parameter tractable when parameterized by the size of . Finally, we consider the parameterized complexity of the CGMproblem; we give a fixed-parameter algorithm for graphs of bounded treewidth, and show that the problem is W[2]-hard when parameterized by , even if the input graph has diameter . [Copyright &y& Elsevier]

Abstract: A simple algorithm for computing an approximate parameterization of real space algebraic curves using their graphs of critical points is designed and studied in this paper. The first step is determining a suitable space graph which contains all critical points of a real algebraic space curve implicitly defined as the complete intersection of two surfaces. The construction of this graph is based on one projection of in a general position onto an -plane and on an intentional choice of vertices. The second part of the designed method is a computation of a spline curve which replaces the edges of the constructed graph by segments of a chosen free-form curve. This step is formulated as an optimization problem when the objective function approximates the integral of the squared Euclidean distance of the constructed approximate curve to the intersection curve. The presented method, based on combining symbolic and numerical steps to the approximation problem, provides approximate parameterizations of space algebraic curves from a small number of approximating arcs. It may serve as a first step to several problems originating in technical practice where approximation curve parameterizations are needed. [Copyright &y& Elsevier]

Abstract: For a polygon P with n vertices, the vertex guarding problem asks for the minimum subset G of Pʼs vertices such that every point in P is seen by at least one point in G. This problem is NP-complete and APX-hard. The first approximation algorithm (Ghosh, 1987) involves decomposing P into cells that are equivalence classes for visibility from the vertices of P. This discretized problem can then be treated as an instance of Set Cover and solved in time with a greedy -approximation algorithm. Ghosh (2010) recently revisited the algorithm, noting that minimum visibility decompositions for simple polygons (Bose et al., 2000) have only cells, improving the running time of the algorithm to for simple polygons. In this paper we observe that, since minimum visibility decompositions for simple polygons have only sinks (i.e., cells of minimal visibility) (Bose et al., 2000), the running time of the algorithm can be further improved to . We then extend the result of Bose et al. to polygons with holes, showing that a minimum visibility decomposition of a polygon with h holes has only cells and only cells of minimal visibility. We exploit this result to obtain a faster algorithm for vertex guarding polygons with holes. We then show that, in the same time complexity, we can attain approximation factors of for simple polygons and for polygons with holes. [Copyright &y& Elsevier]

Abstract: Different kinds of algorithms can be chosen so as to compute elementary functions. Among all of them, it is worthwhile mentioning the shift-and-add algorithms due to the fact that they have been specifically designed to be very simple and to save computer resources. In fact, almost the only operations usually involved with these methods are additions and shifts, which can be easily and efficiently performed by a digital processor. Shift-and-add algorithms allow fairly good precision with low cost iterations. The most famous algorithm belonging to this type is CORDIC. CORDIC has the capability of approximating a wide variety of functions with only the help of a slight change in their iterations. In this paper, we will analyze the requirements of some engineering and industrial problems in terms of type of operands and functions to approximate. Then, we will propose the application of shift-and-add algorithms based on CORDIC to these problems. We will make a comparison between the different methods applied in terms of the precision of the results and the number of iterations required. [Copyright &y& Elsevier]

Abstract: An extensive literature in economics and social science addresses contests, in which players compete to outperform each other on some measurable criterion, often referred to as a player’s score, or output. Players incur costs that are an increasing function of score, but receive prizes for obtaining higher score than their competitors. In this paper we study finite games that are discretized contests, and the problems of computing exact and approximate Nash equilibria. Our motivation is the worst-case hardness of Nash equilibrium computation, and the resulting interest in important classes of games that admit polynomial-time algorithms. For games that have a tie-breaking rule for players’ scores, we present a polynomial-time algorithm for computing an exact equilibrium in the 2-player case, and for multiple players, a characterization of Nash equilibria that shows an interesting parallel between these games and unrestricted 2-player games in normal form. When ties are allowed, via a reduction from these games to a subclass of anonymous games, we give approximation schemes for two special cases: constant-sized set of strategies, and constant number of players. [Copyright &y& Elsevier]

Abstract: In this paper, an algorithm to construct -point (for any integer ) binary approximating subdivision schemes has been developed using the Cox–de Boor recursion formula. Some properties like symmetry of basis functions and polynomial reproduction are also discussed. It can be observed that most of the existing binary approximating schemes (corner cutting scheme developed by Chaikin, and 3-point, 4-point, 5-point and 6-point schemes introduced by Siddiqi and Ahmad) are either special cases or can be reproduced by the proposed algorithm. [Copyright &y& Elsevier]

Abstract: Event-based sequences are a kind of pattern based on temporal associations with two essential characteristics: they are syntactically simple and have a great expressive power. For this reason, event-based sequence mining is an interesting solution to the problem of knowledge discovery in dynamic domains, mainly characterized by a time-varying nature. The inter-transactional model has led to the design of algorithms aimed to obtain this sort of patterns from time-stamped datasets. These algorithms extend the well-known Apriori algorithm, by explicitly adding the temporal context where associations among frequent events occurs. This leads to the possibility of extracting a larger number of patterns with a potential interest in decision making. However, its usefulness is diminished in those datasets where the characteristics of variability and uncertainty are present, which is a common issue in real domains. This is due to the rigidity of the counting method, which uses an exact measure of distance between temporal events. As a solution, we propose a generalization of the temporal mining process, which implies a relaxation of the counting method including the concept of approximate temporal distance between events. In particular, in this paper we present an algorithm, called TSET fuzzy -Miner, which incorporates a fuzzy-based counting technique in order to extract general, flexible, and practical temporal patterns taking into account the particular characteristics of real domains. [Copyright &y& Elsevier]

Abstract: Approximate string matching is one of the most important technologies in the field of computer science, and it is widely used in network security, computational biology, information retrieval, spelling correction and other areas. In these areas, there are huge amounts of data need to be addressed in time. So it requires a high- performance string matching algorithm. At the same time, with the introduction of Compute Unified Device Architecture (CUDA), the general-purpose computing of Graphic Processing Unit (GPU) extended to more applications. This paper proposed a bit-parallel multiple approximate string match algorithm, and developed a GPU implementation which achieved speedups about 28 relative to a single-thread CPU code. [Copyright &y& Elsevier]

Abstract: In this paper, we analyze an algorithm to compute a low-rank approximation of the similarity matrix introduced by Blondel et al. in [1]. This problem can be reformulated as an optimization problem of a continuous function where S is constrained to have unit Frobenius norm, and is a non-negative linear map. We restrict the feasible set to the set of matrices of unit Frobenius norm with either k nonzero identical singular values or at most k nonzero (not necessarily identical) singular values. We first characterize the stationary points of the associated optimization problems and further consider iterative algorithms to find one of them. We analyze the convergence properties of our algorithm and prove that accumulation points are stationary points of . We finally compare our method in terms of speed and accuracy to the full rank algorithm proposed in [1]. [Copyright &y& Elsevier]

Abstract: In this paper, a new definition of a reduced Padé approximant and an algorithm for its computation are proposed. Our approach is based on the investigation of the kernel structure of the Toeplitz matrix. It is shown that the reduced Padé approximant always has nice properties which the classical Padé approximant possesses only in the normal case. The new algorithm allows us to avoid the appearance of Froissart doublets induced by computer roundoff in the non-normal Padé table. [Copyright &y& Elsevier]

Abstract: A deflated restarting Krylov subspace method for approximating a function of a matrix times a vector is proposed. In contrast to other Krylov subspace methods, the performance of the method in this paper is better. We further show that the deflating algorithm inherits the superlinear convergence property of its unrestarted counterpart for the entire function and present the results of numerical experiments. [Copyright &y& Elsevier]

Abstract: Pythagorean hodograph curves (shortly PH curves), introduced in Farouki and Sakkalis (1990), form an important subclass of polynomial parametric curves and currently represent standard objects in geometric modelling. In this paper, we focus on Tschirnhausen cubic as the only one Pythagorean hodograph cubic and we study planar Hermite interpolation with two arcs of Tschirnhausen cubic joined with continuity (the so-called TC-biarc). We extend results presented in Farouki and Peters (1996) in several ways. We study an asymptotical behaviour of the conversion of an arbitrary planar curve with well defined tangent vectors everywhere to a PH cubic spline curve and we prove that the approximation order is 3. Further, we analyze the shape of TC-biarcs and provide a sufficient condition for input data guaranteeing TC-biarc without local and pairwise self-intersections. Finally, we generalize the basic uniform method to the non-uniform case, which introduces a free shape parameter, and we formulate an algorithm for a suitable choice of this shape parameter such that the corresponding non-uniform TC-biarc is without local and pairwise self-intersections (if such a parameter exists). [Copyright &y& Elsevier]

Abstract: Many sequence analysis tasks can be accomplished with a suffix array, and several of them additionally need the longest common prefix array. In large scale applications, suffix arrays are being replaced with full-text indexes that are based on the Burrows–Wheeler transform. In this paper, we present the first algorithm that computes the longest common prefix array directly on the wavelet tree of the Burrows–Wheeler transformed string. It runs in linear time and a practical implementation requires approximately 2.2 bytes per character. [Copyright &y& Elsevier]

Abstract: We introduce a new type of meshes called 5–6–7 meshes. For many mesh processing tasks, low- or high-valence vertices are undesirable. At the same time, it is not always possible to achieve complete vertex valence regularity, i.e. to only have valence-6 vertices. A 5–6–7 mesh is a closed triangle mesh where each vertex has valence 5, 6, or 7. An intriguing question is whether it is always possible to convert an arbitrary mesh into a 5–6–7 mesh. In this paper, we answer the question in the positive. We present a 5–6–7 remeshing algorithm which converts a closed triangle mesh with arbitrary genus into a 5–6–7 mesh which (a) closely approximates the original mesh geometrically, e.g. in terms of feature preservation and (b) has a comparable vertex count as the original mesh. We demonstrate the results of our remeshing algorithm on meshes with sharp features and different topology and complexity. [Copyright &y& Elsevier]

Abstract: Convection of a scalar quantity by a compressible velocity field may give rise to unbounded solutions or nonphysical overshoots at the continuous and discrete level. In this paper, we are concerned with solving continuity equations that govern the evolution of volume fractions in Eulerian models of disperse two-phase flows. An implicit Galerkin finite element approximation is equipped with a flux limiter for the convective terms. The fully multidimensional limiting strategy is based on a flux-corrected transport (FCT) algorithm. This nonlinear high-resolution scheme satisfies a discrete maximum principle for divergence-free velocities and ensures positivity preservation for arbitrary velocity fields. To enforce an upper bound that corresponds to the maximum-packing limit, an FCT-like overshoot limiter is applied to the converged convective fluxes at the end of each time step. This postprocessing step imposes an additional physical constraint on the numerical solution to the unconstrained mathematical model. Numerical results for 2D implosion problems illustrate the performance of the proposed limiting procedure. [Copyright &y& Elsevier]

Abstract: Piezoelectric fuel injectors will require closed-loop control to realize tightly spaced injections. This paper describes an estimation algorithm for cycle-to-cycle determination of an injection flow profile for use as feedback for closed-loop control. A control design-amenable, 2-pulse approximate model is outlined to represent the dynamics of simultaneously controlling the quantity of, and realized dwell time between, injection pulses. A control law is developed to provide an overdamped response of realized dwell time to prevent pulse bleeding. Closed-loop performance is validated with the experimental data. Desired fuel quantity, and very short dwell times of 0.0002s (two crank angle degrees at 1800RPM), are realized with tracking error convergence time constants of approximately four engine cycles (0.27s at 1800RPM). [Copyright &y& Elsevier]

Abstract: This paper describes the identification of Wiener–Hammerstein models and two recently suggested algorithms are applied to the SYSID''09 benchmark data. The most difficult step in the identification process of such block-oriented models is to generate good initial values for the linear dynamic blocks so that local minima are avoided. Both of the considered algorithms obtain good initial estimates by using the best linear approximation (BLA) which can easily be estimated from data. Given the BLA, the two algorithms differ in the way the dynamics are separated into two linear parts. The first algorithm simply considers all possible splits of the dynamics. Each of the splits is used to initialize one Wiener–Hammerstein model using linear least-squares and the best performing model is selected. In the second algorithm, both linear blocks are initialized with the entire BLA model using basis function expansions of the poles and zeros of the BLA. This gives over-parameterized linear blocks and their order is decreased in a model reduction step. Both algorithms are explained and their properties are discussed. They both give good, comparable models on the benchmark data. [Copyright &y& Elsevier]

Abstract: In this paper the Wiener–Hammerstein Benchmark is identified as a bilinear discrete system. The bilinear approximation relies on both facts that the Wiener–Hammerstein system can be described by a Volterra series which can be approximated by bilinear systems. The identification is performed with an iterative bilinear subspace identification algorithm previously proposed by the authors. In order to increase accuracy, polynomial static nonlinearities were added to the bilinear model input. These Hammerstein type bilinear models are then identified using the same iterative subspace identification algorithm. [Copyright &y& Elsevier]

Abstract: This paper addresses new algorithms for constructing weighted cubic splines that are very effective in interpolation and approximation of sharply changing data. Such spline interpolations are a useful and efficient tool in computer-aided design when control of tension on intervals connecting interpolation points is needed. The error bounds for interpolating weighted splines are obtained. A method for automatic selection of the weights is presented that permits preservation of the monotonicity and convexity of the data. The weighted B-spline basis is also well suited for generation of freeform curves, in the same way as the usual B-splines. By using recurrence relations we derive weighted B-splines and give a three-point local approximation formula that is exact for first-degree polynomials. The resulting curves satisfy the convex hull property, they are piecewise cubics, and the curves can be locally controlled with interval tension in a computationally efficient manner. [Copyright &y& Elsevier]

Abstract: This paper presents a new algorithm for fast approximate surface reconstruction from sampled points. This algorithm works over three steps. Firstly, a raw rectangular surface is obtained, and then this surface is triangulated and smoothed in the second step. The surface vertices are fitted to the nearest input points at the end. The algorithm is very fast, numerically stable, easy to implement, and it constructs a watertight surface. In the experimental section, the algorithm is compared with other available algorithms (algorithm from CGAL library, Power Crust, Tight cocone, and Poisson reconstruction) in regards to the spent CPU time. Finally, an error of the obtained approximate surface is empirically estimated. [Copyright &y& Elsevier]

Abstract: Q-Learning is based on value iteration and remains the most popular choice for solving Markov Decision Problems (MDPs) via reinforcement learning (RL), where the goal is to bypass the transition probabilities of the MDP. Approximate policy iteration (API) is another RL technique, not as widely used as Q-Learning, based on modified policy iteration. In this paper, we present and analyze an API algorithm for discounted reward based on (i) a classical temporal differences update for policy evaluation and (ii) simulation-based mean estimation for policy improvement. Further, we analyze for convergence API algorithms based on Q-factors for (i) discounted reward and (ii) for average reward MDPs. The average reward algorithm is based on relative value iteration; we also present results from some numerical experiments with it. [Copyright &y& Elsevier]

Abstract: This paper presents a new algorithm for constructing the approximation of a polygon’s medial axis. The algorithm works in three steps. Firstly, constrained Delaunay triangulation of a polygon is done. After that, the obtained triangulation is heuristically corrected by inserting Steiner points. Finally, the obtained triangles are classified into three classes, thus enabling the construction of the polygon’s medial axis. As shown by experiments, the obtained approximate polygon medial axis has better properties than those methods based on a Voronoi diagram. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the checkpoint problem. The input consists of an undirected graph , a set of source–destination pairs , and a collection of paths connecting the pairs. A feasible solution is a multicut , namely, a set of edges whose removal disconnects every source–destination pair. For each we define . In the sum checkpoint (SCP) problem the goal is to minimize , while in the maximum checkpoint (MCP) problem the goal is to minimize . These problems have several natural applications, e.g., in urban transportation and network security. In a sense, they combine the multicut problem and the minimum membership set cover problem. For the sum objective we show that weighted SCP is equivalent, with respect to approximability, to undirected multicut. Thus there exists an approximation for SCP in general graphs. Our current approximability results for the max objective have a wide gap: we provide an approximation factor of for MCP and a hardness of 2 under the assumption . The hardness holds for trees. This solves an open problem of Nelson (2009) . We complement the lower bound by an almost matching upper bound with an asymptotic approximation factor of 2. On trees with all having an ancestor–descendant relation, we give a combinatorial exact algorithm. Besides the algorithm being combinatorial, its running time improves by many orders of magnitude the LP algorithm that follows from total unimodularity. Finally, we show strong hardness for the well-known problem of finding a path with minimum forbidden pairs, which in a sense can be considered the dual to the checkpoint problem. Despite various works on this problem, hardness of approximation was not known prior to this work. We show that the problem cannot be approximated within for some constant , unless . This is the strongest type of hardness possible. It carries over to directed acyclic graphs and is a huge improvement over the plain -hardness of Gabow [H.N. Gabow, Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput. 36 (6) (2007) 1648–1671]. [Copyright &y& Elsevier]

Abstract: In this paper, we prove that an existing algorithm with periodical impulses for chaos suppression in continuous systems can be further extended and successfully applied to a class of piecewise continuous systems. For this purpose, the underlying initial value problem is transformed into a continuous problem via Filippov regularization and Cellina’s approximation theorem. Next, some results on existence and continuation for ODEs with impulses are applied. As an example, the piece-wise continuous Chen system is considered. [Copyright &y& Elsevier]

Abstract: In this paper, we present a numerical approach for solving the system of multi-pantograph equations with mixed conditions. This system is usually difficult to solve analytically. By expanding the approximate solutions by means of the Bessel functions of first kind with unknown coefficients, the proposed approach consists of reducing the problem to a linear algebraic equation system. The unknown coefficients of the Bessel functions of first kind are computed using the matrix operations of derivatives together with the collocation method. An error estimation is given. The reliability and efficiency of the proposed scheme are demonstrated by some numerical examples. All of the numerical computations have been performed on a computer with the aid of a program written in Matlab. [Copyright &y& Elsevier]

Abstract: In this paper we consider imprecise terrains, that is, triangulated terrains with a vertical error interval in the vertices. In particular, we study the problem of removing as many local extrema (minima and maxima) as possible from the terrain; that is, finding an assignment of one height to each vertex, within its error interval, so that the resulting terrain has minimum number of local extrema. We show that removing only minima or only maxima can be done optimally in time, for a terrain with n vertices. Interestingly, however, the problem of finding a height assignment that minimizes the total number of local extrema (minima as well as maxima) is NP-hard, and is even hard to approximate within a factor of unless . Moreover, we show that even a simplified version of the problem where we can have only three different types of intervals for the vertices is already NP-hard, a result we obtain by proving hardness of a special case of 2-Disjoint Connected Subgraphs, a problem that has lately received considerable attention from the graph-algorithms community. [Copyright &y& Elsevier]

Abstract: The voting rules proposed by Dodgson and Young are both designed to find an alternative closest to being a Condorcet winner, according to two different notions of proximity; the score of a given alternative is known to be hard to compute under either rule. In this paper, we put forward two algorithms for approximating the Dodgson score: a combinatorial, greedy algorithm and an LP-based algorithm, both of which yield an approximation ratio of , where m is the number of alternatives and is the st harmonic number. We also prove that our algorithms are optimal within a factor of 2, unless problems in have quasi-polynomial-time algorithms. Despite the intuitive appeal of the greedy algorithm, we argue that the LP-based algorithm has an advantage from a social choice point of view. Further, we demonstrate that computing any reasonable approximation of the ranking produced by Dodgsonʼs rule is -hard. This result provides a complexity-theoretic explanation of sharp discrepancies that have been observed in the social choice theory literature when comparing Dodgson elections with simpler voting rules. Finally, we show that the problem of calculating the Young score is -hard to approximate by any factor. This leads to an inapproximability result for the Young ranking. [Copyright &y& Elsevier]

Abstract: An essential task in comparative genomics is to decompose two or more genomes into synteny blocks that are segments of chromosomes with similar contents. Given a set of genomic maps each containing the same markers without duplicates, the problem Maximal Strip Recovery (MSR) aims at finding a decomposition of the genomic maps into synteny blocks (strips) of the maximum total length , by deleting the minimum number of markers which are probably noise and ambiguities. In this paper, we present a collection of new or improved FPT and approximation algorithms for MSR and its variants. Our main results include a time FPT algorithm for -gap-MSR-, a time FPT algorithm for both CMSR- and -gap-CMSR-, and a -approximation algorithm for both CMSR- and -gap-CMSR-. [Copyright &y& Elsevier]

Abstract: In Problems with large deformation including fracture and fragmentation, the grid based methods have some limitations which make them unsuitable for simulating these types of problems. An example is extreme mesh distortion in a lagrangian approach like Finite element method. Another situation is the inability of Eulerian based formulations in tracking the history of a desired physical property at the interface of multi materials including impact problems. A promising solution is taking the advantage of meshless and particle based methods which do not use any kind of grid in the physical domain of problem. In this paper, corrective smoothed particle algorithm (CSPM) as a meshless particle method is used to study the mechanical behavior of a ceramic–metal functionally graded material (FGM) under high velocity impact conditions. A mixed strength model with sigmoid formulation has been used to describe both yielding and fracture phenomena in the FGM. The strength model includes the JC dynamic yield relation and Johnson–Holmquist–Beissel (JHB) fracture model with a continuum damage description approach. An efficient renormalization in continuity density approach is used to improve the smoothed particle hydrodynamics (SPH) approximation of boundary physical variables. This study shows that CSPM in combination with the proper strength model describing the FGM dynamic behavior, can predict the mixed plastic and brittle response of a ceramic–metal functionally graded material under high impact velocities. [Copyright &y& Elsevier]

Abstract: In this paper, we apply the wavelet-Galerkin method to obtain approximate solutions to linear Volterra integral equations (VIEs) of the second kind. Daubechies wavelets are used to find such approximations. In this approach, we introduce some new connection coefficients and discuss their properties and propose algorithms to evaluate them. These coefficients can be computed just once and applied for solving every linear VIE of the second kind. Convergence and error analysis are discussed and numerical examples illustrate the efficiency of the method. [Copyright &y& Elsevier]

Abstract: This paper presents a new ‘Parareal-algorithm’ to solve time-dependent ODEs parallel in time. The algorithm approximates the solutions later in time simultaneously with the solutions earlier in time. To approximate the solutions simultaneously, an optimization problem is constructed and solved using gradient based techniques. The accurate gradients are evaluated using adjoints. Promising results are obtained when the interval of interest is split into suffciently small subintervals. [Copyright &y& Elsevier]

Abstract: This paper describes an extremely fast polynomial time algorithm, the Near Optimal Vertex Cover Algorithm (NOVCA) that produces an optimal or near optimal vertex cover for any known undirected graph G (V, E). NOVCA constructs the vertex cover by repeatedly adding, at each step, all vertices adjacent to the vertex of minimal degree; in the case of a tie, it selects the one having the maximum sum of degrees of its neighbors. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any other available vertex cover algorithms. [Copyright &y& Elsevier]