Search

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: 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: 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: 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: 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: In the context of designing a scalable overlay network to support decentralized topic-based pub/sub communication, the Minimum Topic-Connected Overlay problem (Min-TCO in short) has been investigated: given a set of topics and a collection of users together with the lists of topics they are interested in, the aim is to connect these users to a network by a minimum number of edges such that every graph induced by users interested in a common topic is connected. It is known that Min-TCO is -hard and approximable within in polynomial time. In this paper, we further investigate the problem and some of its special instances. We give various hardness results for instances where the number of topics in which a user is interested in is bounded by a constant, and also for the instances where the number of users interested in a common topic is a constant. For the latter case, we present a first constant approximation algorithm. We also present some polynomial-time algorithms for very restricted instances of Min-TCO. [Copyright &y& Elsevier]

Abstract: The Consensus Clustering problem has been introduced as an effective way to analyze the results of different microarray experiments (Filkov and Skiena (2004a,b) . The problem asks for a partition that summarizes a set of input partitions (each corresponding to a different microarray experiment) under a simple and intuitive cost. The problem on instances with two input partitions has a simple polynomial time algorithm, but it becomes APX-hard on instances with three input partitions. The quest for defining the boundary between tractable and intractable instances leads to the investigation of the restriction of Consensus Clustering when the output partition contains a fixed number of sets. In this paper, we give a randomized polynomial time approximation scheme for such problems, while proving its NP-hardness even for 2 output partitions, therefore definitively settling the approximation complexity of the problem. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce an algorithm and a computer code for numerical differentiation of discrete functions. The algorithm presented is suitable for calculating derivatives of any degree with any arbitrary order of accuracy over all the known function sampling points. The algorithm introduced avoids the labour of preliminary differencing and is in fact more convenient than using the tabulated finite difference formulas, in particular when the derivatives are required with high approximation accuracy. Moreover, the given Matlab computer code can be implemented to solve boundary-value ordinary and partial differential equations with high numerical accuracy. The numerical technique is based on the undetermined coefficient method in conjunction with Taylor’s expansion. To avoid the difficulty of solving a system of linear equations, an explicit closed form equation for the weighting coefficients is derived in terms of the elementary symmetric functions. This is done by using an explicit closed formula for the Vandermonde matrix inverse. Moreover, the code is designed to give a unified approximation order throughout the given domain. A numerical differentiation example is used to investigate the validity and feasibility of the algorithm and the code. It is found that the method and the code work properly for any degree of derivative and any order of accuracy. [Copyright &y& Elsevier]

Abstract: This paper considers bi-criteria scheduling on a single parallel-batch machine to minimizing two regular scheduling criteria that are non-decreasing in the job completion times. For minimizing the total weighted completion time and the makespan simultaneously, we prove that the problem is NP-hard in the ordinary sense and possesses a fully polynomial-time approximation scheme. For minimizing the weighted total number of tardy jobs and the makespan simultaneously, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme. Furthermore, we identify that all Pareto-optimal solutions for and can be found in pseudo-polynomial time, respectively. [Copyright &y& Elsevier]

Abstract: Weighted essentially non-oscillatory (WENO) schemes have been mainly used for solving hyperbolic partial differential equations (PDEs). Such schemes are capable of high order approximation in smooth regions and non-oscillatory sharp resolution of discontinuities. The base of the WENO schemes is a non-oscillatory WENO approximation procedure, which is not necessarily related to PDEs. The typical WENO procedures are WENO interpolation and WENO reconstruction. The WENO algorithm has gained much popularity but the basic idea of approximation did not change much over the years. In this paper, we first briefly review the idea of WENO interpolation and propose a modification of the basic algorithm. New approximation should improve basic characteristics of the approximation and provide a more flexible framework for future applications. New WENO procedure involves a binary tree weighted construction that is based on key ideas of WENO algorithm and we refer to it as the binary weighted essentially non-oscillatory (BWENO) approximation. New algorithm comes in a rational and a polynomial version. Furthermore, we describe the WENO reconstruction procedure, which is usually involved in the numerical schemes for hyperbolic PDEs, and propose the new reconstruction procedure based on the described BWENO interpolation. The obtained numerical results show that the newly proposed procedures perform very well on the considered test examples. [Copyright &y& Elsevier]

Abstract: This paper presents three proposals of multiobjective memetic algorithms to solve a more realistic extension of a classical industrial problem: time and space assembly line balancing. These three proposals are, respectively, based on evolutionary computation, ant colony optimisation, and greedy randomised search procedure. Different variants of these memetic algorithms have been developed and compared in order to determine the most suitable intensification–diversification trade-off for the memetic search process. Once a preliminary study on nine well-known problem instances is accomplished with a very good performance, the proposed memetic algorithms are applied considering real-world data from a Nissan plant in Barcelona (Spain). Outstanding approximations to the pseudo-optimal non-dominated solution set were achieved for this industrial case study. [Copyright &y& Elsevier]

Abstract: In this paper we show that the problem of identifying an edge of a graph such that there exists an optimal vertex cover of containing exactly one of the vertices and is NP-hard. Such an edge is called a weak edge. We then develop a polynomial time approximation algorithm for the vertex cover problem with performance guarantee , where is an upper bound on a measure related to a weak edge of a graph. A related problem of identifying an edge such that there exists an optimal vertex cover containing both vertices and is also shown to be NP-hard. Further, we discuss a new relaxation of the vertex cover problem which is used in our approximation algorithm to obtain smaller values of . We also obtain linear programming representations of the vertex cover problem on special graphs. [Copyright &y& Elsevier]

Abstract: The majority of clustering methods that have been proposed in the literature are focused on classification problems, and more specifically on pattern recognition problems. In this paper, we provide an enhanced clustering function approximation (ECFA) methodology that is especially suited for function approximation problems, which calculates the error committed in every cluster using the real output of the radial basis function neural network (RBFN), and not just an approximate value of that output, trying to concentrate more clusters in those input regions where the approximation error is bigger, thus attempting to homogenize the contribution to the error of every cluster. ECFA migrates clusters to the zones of the input space where the approximation error is bigger, thus trying to homogenously distribute the total distortion in every cluster, producing a better share-out of clusters for the data input space. We will see that ECFA outperforms other clustering techniques, such as the FCM algorithm or the CFA algorithm not only with respect to the final approximation error but also with respect to the execution time. [Copyright &y& Elsevier]

Abstract: The problem of finding the least change adjustment to a stiffness matrix modeled by finite element method is considered in this paper. Desired stiffness matrix properties such as symmetry, sparsity, positive semidefiniteness, and satisfaction of the characteristic equation are imposed as side constraints of the constructed optimal matrix approximation for updating the stiffness matrix, which matches measured data better. The dual problems of the original constrained minimization are presented and solved by subgradient algorithms with different line search strategies. Some numerical results are included to illustrate the performance and application of the proposed methods. [Copyright &y& Elsevier]

Abstract: Nonnegative matrix factorization (NMF), the problem of approximating a nonnegative matrix with the product of two low-rank nonnegative matrices, has been shown to be useful in many applications, such as text mining, image processing, and computational biology. In this paper, we explain how algorithms for NMF can be embedded into the framework of multilevel methods in order to accelerate their initial convergence. This technique can be applied in situations where data admit a good approximate representation in a lower dimensional space through linear transformations preserving nonnegativity. Several simple multilevel strategies are described and are experimentally shown to speed up significantly three popular NMF algorithms (alternating nonnegative least squares, multiplicative updates and hierarchical alternating least squares) on several standard image datasets. [Copyright &y& Elsevier]

Abstract: The Minimum Length Polygon (MLP) is an interesting first order approximation of a digital contour. For instance, the convexity of the MLP is characteristic of the digital convexity of the shape, its perimeter is a good estimate of the perimeter of the digitized shape. We present here two novel equivalent definitions of MLP, one arithmetic, one combinatorial, and both definitions lead to two different linear time algorithms to compute them. This paper extends the work presented in Provençal and Lachaud (2009) , by detailing the algorithms and providing full proofs. It includes also a comparative experimental evaluation of both algorithms showing that the combinatorial algorithm is about 5 times faster than the other. We also checked the multigrid convergence of the length estimator based on the MLP. [Copyright &y& Elsevier]

Abstract: In the present paper, we present block Arnoldi-based methods for the computation of low rank approximate solutions of large discrete-time algebraic Riccati equations (DARE). The proposed methods are projection methods onto block or extended block Krylov subspaces. We give new upper bounds for the norm of the error obtained by applying these block Arnoldi-based processes. We also introduce the Newton method combined with the block Arnoldi algorithm and present some numerical experiments with comparisons between these methods. [Copyright &y& Elsevier]

Abstract: The Jacobian-free Newton–Krylov (JFNK) method is a special kind of Newton–Krylov algorithm, in which the matrix-vector product is approximated by a finite difference scheme. Consequently, it is not necessary to form and store the Jacobian matrix. This can greatly improve the efficiency and enlarge the application area of the Newton–Krylov method. The finite difference scheme has a strong influence on the accuracy and robustness of the JFNK method. In this paper, several methods for approximating the Jacobian-vector product, including the finite difference scheme and the finite difference step size, are analyzed and compared. Numerical results are given to verify the effectiveness of different finite difference methods. [Copyright &y& Elsevier]