Search

Abstract: In this paper we present stabilized finite element methods to discretize in space the monochromatic radiation transport equation. These methods are based on the decomposition of the unknowns into resolvable and subgrid scales, with an approximation for the latter that yields a problem to be solved for the former. This approach allows us to design the algorithmic parameters on which the method depends, which we do here when the discrete ordinates method is used for the directional approximation. We concentrate on two stabilized methods, namely, the classical SUPG technique and the orthogonal subscale stabilization. A numerical analysis of the spatial approximation for both formulations is performed, which shows that they have a similar behavior: they are both stable and optimally convergent in the same mesh-dependent norm. A comparison with the behavior of the Galerkin method, for which a non-standard numerical analysis is done, is also presented. [ABSTRACT FROM AUTHOR]

Abstract: The lower and upper approximations are basic concepts in rough fuzzy set theory. The effective computation of approximations is very important for improving the performance of related algorithms. This paper proposed and proved two incremental methods for fast computing the rough fuzzy approximations, one starts from the boundary set, the other is based on the cut sets of a fuzzy set. Then some illustrative examples are conducted. Consequently, two algorithms corresponding to the two incremental methods are put forward respectively. In order to test the efficiency of algorithms, some experiments are made on a large soybean data set from UCI. The experimental results show that the two incremental methods effectively reduce the computing time in comparison with the traditional non-incremental method [1]. [ABSTRACT FROM AUTHOR]

Abstract: We propose a new second-order cone linear complementarity problem (SOCLCP) formulation for the numerical finite element analysis of three-dimensional (3D) frictional contact problems by the parametric variational principle. Specifically, we develop a regularization technique to resolve the multi-valued difficulty involved in the frictional contact law, and use a second-order cone complementarity condition to handle the regularized Coulomb friction law in contact analysis. The governing equations of the 3D frictional contact problem is represented by an SOCLCP via the parametric variational principle and the finite element method, which avoids the polyhedral approximation to the Coulomb friction cone so that the problem to be solved has much smaller size and the solution has better accuracy. In this paper, we reformulate the SOCLCP as a semi-smooth system of equations via a one-parametric class of second-order cone complementarity functions, and then apply the non-smooth Newton method for solving this system. Numerical results confirm the effectiveness and robustness of the SOCLCP approach developed. [ABSTRACT FROM AUTHOR]

Abstract: We consider the minimum rainbow subgraph problem (MRS): given a graph , whose edges are coloured with colours. Find a subgraph of of minimum order and with edges such that each colour occurs exactly once. For graphs with maximum degree there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of . In this paper we present a polynomial-time approximation algorithm with an approximation ratio of for . [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study the problem where an optimal solution of a knapsack problem on items is known and a very small number of new items arrive. The objective is to find an optimal solution of the knapsack problem with items, given an optimal solution on the items (reoptimization of the knapsack problem). We show that this problem, even in the case , is NP-hard and that, in order to have effective heuristics, it is necessary to consider not only the items included in the previously optimal solution and the new items, but also the discarded items. Then, we design a general algorithm that makes use, for the solution of a subproblem, of an -approximation algorithm known for the knapsack problem. We prove that this algorithm has a worst-case performance bound of , which is always greater than , and therefore that this algorithm always outperforms the corresponding -approximation algorithm applied from scratch on the items. We show that this bound is tight when the classical Ext-Greedy algorithm and the algorithm are used to solve the subproblem. We also show that there exist classes of instances on which the running time of the reoptimization algorithm is smaller than the running time of an equivalent PTAS and FPTAS. [ABSTRACT FROM AUTHOR]

Abstract: There is no known algorithm that solves the general case of the approximate edit distance problem, where the edit operations are insertion, deletion, mismatch, and swap, in time , where is the length of the text and is the length of the pattern. In the effort to study this problem, the edit operations have been analyzed independently. Karloff  showed an algorithm that approximates the edit distance problem with only the mismatch operation in time . Amir et al. showed that if the only edit operations allowed are swap and mismatch, then the exact edit distance problem can be solved in time . In this paper, we discuss the problem of approximate edit distance with swap and mismatch. We show a randomized time algorithm for the problem. The algorithm guarantees an approximation factor of with probability of at least . [ABSTRACT FROM AUTHOR]

Abstract: Clustering analysis has been applied in a wild variety of fields such as biology, medicine, economics, etc. For time series clustering, dimension reduction methods like data sampling or piecewise aggregate approximation (PAA) algorithm are often applied to reduce data dimension before clustering. Consequently, the information of subsequence may be overlooked. Nevertheless, some properties of time series with the same sampling data may result in different clustering results after considering the subsequence information. In this paper, we propose a novel two-level clustering method named 2LTSC (two-level time series clustering), which considers both the whole time series, denoted as level-1 in the first level, and the subsequence information of time series, denoted as level-2 in the second level. The data length of level-2 could be different and thus is also considered in the second level in the proposed 2LTSC method. Through experimental evaluation, it is shown that the proposed two-level clustering method, which considers two different time granules at the same time, can provide different and deeper viewpoints for time series clustering analysis. [Copyright &y& Elsevier]

Abstract: In this paper a new efficient algorithm for spherical interpolation of large scattered data sets is presented. The solution method is local and involves a modified spherical Shepard’s interpolant, which uses zonal basis functions as local approximants. The associated algorithm is implemented and optimized by applying a nearest neighbour searching procedure on the sphere. Specifically, this technique is mainly based on the partition of the sphere in a suitable number of spherical zones, the construction of spherical caps as local neighbourhoods for each node, and finally the employment of a spherical zone searching procedure. Computational cost and storage requirements of the spherical algorithm are analyzed. Moreover, several numerical results show the good accuracy of the method and the high efficiency of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, we present a new algorithm to solve general linear fifth-order boundary value problems (BVPs) in the reproducing kernel space . Representation of the exact solution is given in the reproducing kernel space. Its approximate solution is obtained by truncating the -term of the exact solution. Some examples are displayed to demonstrate the computational efficiency of the method. [Copyright &y& Elsevier]

Abstract: In this paper, we present an orthonormal version of the generalized signal subspace tracking. It is based on an interpretation of the generalized signal subspace as the solution of a constrained minimization task. This algorithm, referred to as the CGST algorithm, guarantees the C x -orthonormality of the estimated generalized signal subspace basis at each iteration which C x denotes the correlation matrix of the sequence x(t). An efficient implementation of the proposed algorithm enhances applicability of it in real time applications. [Copyright &y& Elsevier]

Abstract: In this paper we introduce and study cooperative variants of the Traveling Salesperson Problem. In these problems a salesperson has to make deliveries to customers who are willing to help in the process. Customer cooperativeness may be manifested in several modes: they may assist by approaching the salesperson, by reselling the goods they purchased to other customers, or by doing both. Several objectives are of interest: minimizing the total distance traveled by all of the participants, minimizing the maximal distance traveled by a participant and minimizing the total time until all of the deliveries are made. All of the combinations of cooperation modes and objective functions are considered, both in weighted undirected graphs and in Euclidean space. We show that most of the problems have a constant approximation algorithm, many of the others admit a PTAS, and a few are solvable in polynomial time. On the intractability side we provide NP-hardness proofs and inapproximability factors, some of which are tight. [Copyright &y& Elsevier]

Abstract: Given an -vertex directed graph and a set of requests, we consider assigning a set of edges to each vertex in so that for every request in the union of the edge sets assigned to and contains a path from to . The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinalities of the edge sets assigned to each vertex. This problem has been shown to be NP-hard in general, though it is polynomially solvable for some restricted classes of graphs and restricted request structures, such as bidirectional trees with requests of all pairs of vertices. In this paper, we give an advanced investigation about the difficulty of MCD by focusing on the relationship between its (in)approximability and request structures. We first show that MCD with general has lower and upper bounds on approximation ratio under the assumption . We then assume forms a clique structure, called Subset-Full, which is a natural setting in the context of the application. Interestingly, under this natural setting, MCD becomes 2-approximable, though it has still no polynomial time approximation algorithm whose factor is better than 677/676 unless . Finally, we show that this approximation ratio can be improved to 3/2 for the undirected variant of MCD with Subset-Full. [Copyright &y& Elsevier]

Abstract: In this paper we consider the problem of learning hidden independent cascade social networks using exact value injection queries. These queries involve activating and suppressing agents in the target network. We develop an algorithm that optimally learns an arbitrary social network of size using queries, matching the information theoretic lower bound that we prove for this problem. We also consider the case when the target social network forms a tree and show that the learning problem takes queries. We also give an approximation algorithm for finding an influential set of nodes in the network, without resorting to learning its structure. Finally, we discuss some limitations of our approach, and limitations of path-based methods, when non-exact value injection queries are used. [Copyright &y& Elsevier]

Abstract: Borodin, Nielsen and Rackoff  introduced the class of priority algorithms as a framework for modeling deterministic greedy-like algorithms. In this paper we address the effect of randomization in greedy-like algorithms. More specifically, we consider approximation ratios within the context of randomized priority algorithms. As case studies, we prove inapproximation results for two well-studied optimization problems, namely facility location and makespan scheduling. [Copyright &y& Elsevier]

Abstract: For nonsmooth convex optimization, Robert Mifflin and Claudia Sagastizábal introduce a -space decomposition algorithm in Mifflin and Sagastizábal (2005) . An attractive property of this algorithm is that if a primal–dual track exists, this algorithm uses a bundle subroutine. With the inclusion of a simple line search, it is proved to be globally and superlinearly convergent. However, a drawback is that it needs the exact subgradients of the objective function, which is expensive to compute. In this paper an approximate decomposition algorithm based on proximal bundle-type method is introduced that is capable to deal with approximate subgradients. It is shown that the sequence of iterates generated by the resulting algorithm converges to the optimal solutions of the problem. Numerical tests emphasize the theoretical findings. [Copyright &y& Elsevier]

Abstract: Spread spectrum watermarking (SSW) is one of the most powerful techniques for secure audio or image watermarking. SSW hides information by spreading the spectrum. The hidden information is called the ‘watermark’ and is added to a host signal, making the latter a watermarked signal. The spreading of the spectrum is carried out by using a pseudorandom noise (PN) sequence. In conventional SSW approaches, the receiver must know both the PN sequence used at the transmitter and the location of the watermark in the watermarked signal for detecting the hidden information. This method has contributed much to secure audio watermarking in that any user, who is not able to access this secrete information, cannot detect the hidden information. Detection of the PN sequence is the key issue of hidden information detection in SSW. Although the PN sequence can be reliably detected by means of heuristic approaches, due to the high computational cost of this task, such approaches tend to be too computationally expensive to be practical. Evolutionary Algorithms (EAs) belong to a class of such approaches. Most of the computational complexity involved in the use of EAs arises from fitness function evaluation that may be either very difficult to define or computationally very expensive to evaluate. This paper proposes an approximate model, called Adaptive Fuzzy Fitness Granulation with Fuzzy Supervisor (AFFG-FS), to replace the expensive fitness function evaluation. First, an intelligent guided technique via an adaptive fuzzy similarity analysis for fitness granulation is used for deciding on the use of exact fitness function and dynamically adapting the predicted model. Next, in order to avoid manually tuning parameters, a fuzzy supervisor as auto-tuning algorithm is employed. Its effectiveness is investigated with three traditional optimization benchmarks of four different choices for the dimensionality of the search space. The effect of the number of granules on the rate of convergence is also studied. The proposed method is then extended to the hidden information detection problem to recover a PN sequence with a chip period equal to 63, 127 and 255 bits. In comparison with the standard application of EAs, experimental analysis confirms that the proposed approach has an ability to considerably reduce the computational complexity of the detection problem without compromising performance. Furthermore, the auto-tuning of the fuzzy supervisor removes the need of exact parameter determination. [Copyright &y& Elsevier]

Abstract: In this paper we design and implement rigorous algorithms for computing symbolic dynamics for piecewise-monotone-continuous maps of the interval. The algorithms are based on computing forwards and backwards approximations of the boundary, discontinuity and critical points. We explain how to handle the discontinuities in the symbolic dynamics which occur when the computed partition element boundaries are not disjoint. The method is applied to compute the symbolic dynamics and entropy bounds for the return map of the singular limit of a switching system with hysteresis and the forced Van der Pol equation. [Copyright &y& Elsevier]

Abstract: Many real problems can be modeled to the problems with a hierarchical structure, and bilevel programming is a useful tool to solve the hierarchical optimization problems. So the bilevel programming is widely applied, and numerous methods have been proposed to solve this programming. In this paper, we propose an approximate programming algorithm to solve bilevel nonlinear programming problem. Finally, the example illustrates the feasibility of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: We present a new subdivision scheme (BCC-algorithm) for constructing a surface from an initial net of 3D curves, by repeated refinements of nets of curves. This algorithm improves a subdivision scheme for nets of curves (BC-algorithm), proposed in a previous paper, which generalizes the well known Chaikin subdivision scheme refining control points. While the BC-algorithm generates continuous surfaces, the BCC-algorithm generates surfaces. This is achieved by a corner cutting step following each refinement step of the BC-algorithm. The analysis of convergence, smoothness and approximation order of the BCC-algorithm is based on its proximity to the tensor-product Chaikin scheme. A short discussion of boundary rules for the BCC-algorithm is also included. Several numerical examples, illustrating the operation of the BCC-algorithm, with and without boundary rules, are presented. In the examples the advantage of the BCC-algorithm over the tensor-product Chaikin algorithm is evident. [Copyright &y& Elsevier]

Abstract: This paper discusses optimization of quality measures over first order Delaunay triangulations. Unlike most previous work, our measures relate to edge-adjacent or vertex-adjacent triangles instead of only to single triangles. We give efficient algorithms to optimize certain measures, including measures related to the area ratio of adjacent triangles, angle between outward normals of adjacent triangles (for polyhedral terrains), and number of convex vertices. Some other measures are shown to be NP-hard. These include maximum vertex degree, number of convex edges, and number of mixed vertices. For the latter two measures we provide, for any constant , factor approximation algorithms that run in and time (when the Delaunay triangulation is given). For minimizing the maximum vertex degree, the NP-hardness proof provides an inapproximability result. Our results are presented for the class of first order Delaunay triangulations, but also apply to triangulations where for every triangle at least two edges are fixed. The approximation result on maximizing the number of convex edges is also extended to k-th order Delaunay triangulations. [Copyright &y& Elsevier]

Abstract: In this paper, we propose an efficient -norm () Proximal Support Vector Machine by combining proximal support vector machine (PSVM) and feature selection strategy together. Following two lower bounds for the absolute value of nonzero entries in every local optimal solution of the model, we investigate the relationship between sparsity of the solution and the choice of the regularization parameter and -norm. After smoothing the problem in -norm PSVM, we solved it by smoothing conjugate gradient method (SCG) method, and preliminary numerical experiments show the effectiveness of our model for identifying nonzero entries in numerical solutions and feature selection, and we also apply it to a real-life credit dataset to prove its efficiency. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents an inelastic element for the analysis of beams resting on two-parameter foundations. The element is derived from a two field mixed formulation with independent approximation of forces and displacements. The values for the two parameters of the foundation are derived through an iterative technique that is based on an assumption of plane strain for the soil medium. This iterative behavior is repeated at each time step of the nonlinear solution algorithm. The nonlinear response of structures resting on this improved two-parameter foundation model is analyzed following both a Vlasov and a Pasternak approach. Numerical examples that clarify the advantage of the newly developed model are conducted. These studies confirmed the importance of accounting for the foundation second parameter, and the efficiency and accuracy of the proposed model. [Copyright &y& Elsevier]

Abstract: In this paper, we consider single-machine scheduling problems under the job rejection constraint. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the single machine. However, the total rejection penalty of the rejected jobs cannot exceed a given upper bound. The objective is to find a schedule such that a given criterion is minimized, where is a non-decreasing function on the completion times of the accepted jobs. We analyze the computational complexities of the problems for distinct objective functions and present pseudo-polynomial-time algorithms. In addition, we provide a fully polynomial-time approximation scheme for the makespan problem with release dates. For other objective functions related to due dates, we point out that there is no approximation algorithm with a bounded approximation ratio. [Copyright &y& Elsevier]

Abstract: We consider the sorting buffers problem. Input to this problem is a sequence of requests, each specified by a point in a metric space. There is a “server” that moves from point to point to serve these requests. To serve a request, the server needs to visit the point corresponding to that request. The objective is to minimize the total distance traveled by the server in the metric space. In order to achieve this, the server is allowed to serve the requests in any order that requires to “buffer” at most k requests at any time. Thus a valid reordering can serve a request only after serving all but k previous requests. In this paper, we consider this problem on the line metric which is motivated by its application to the disc scheduling problem. We present first approximation algorithms with non-trivial approximation ratios in both online and offline settings. On a line metric with n uniformly spaced points, we give a randomized online algorithm with a competitive ratio of in expectation against an oblivious adversary. In the offline setting, our algorithm yields the first constant-factor approximation and runs in quasi-polynomial time where N is the total number of requests. Our approach is based on a dynamic program that keeps track of the number of pending requests in each of line segments that are geometrically increasing in length. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of scheduling with release dates and rejection on a single parallel batching machine, where the jobs have non-identical sizes. Our objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs. First, we give a polynomial time approximation scheme (PTAS) for the case where jobs can be split. Then, we propose a -approximation algorithm for the special case with identical release dates. Finally, we present an approximation algorithm for the general problem with worst-case ratio , where is an arbitrarily small constant. [Copyright &y& Elsevier]

Abstract: It is well known that an irreducible algebraic curve is rational (i.e. parametric) if and only if its genus is zero. In this paper, given a tolerance and an ϵ-irreducible algebraic affine plane curve of proper degree d, we introduce the notion of ϵ-rationality, and we provide an algorithm to parametrize approximately affine ϵ-rational plane curves by means of linear systems of -degree curves. The algorithm outputs a rational parametrization of a rational curve of degree d which has the same points at infinity as . Moreover, although we do not provide a theoretical analysis, our empirical analysis shows that and are close in practice. [Copyright &y& Elsevier]

Abstract: In this paper, we develop a discrete approximation method for solving continuous-time linear fractional programming problems. Our method enables one to derive a recurrence structure which shall overcome the computational curse caused by the increasing numbers of decision variables in the approximate decision problems when the subintervals are getting smaller and smaller. Furthermore, our algorithm provides estimation for the error bounds of the approximate solutions. We also establish the convergence of our approximate solutions to the continuous-time linear fractional programming problems. Numerical examples are provided to illustrate the quality of the approximate solutions. [Copyright &y& Elsevier]

Abstract: As is well known, a rank- matrix can be recovered from a cross of linearly independent columns and rows, and an arbitrary matrix can be interpolated on the cross entries. Other entries by this cross or pseudo-skeleton approximation are given with errors depending on the closeness of the matrix to a rank- matrix and as well on the choice of cross. In this paper we extend this construction to -dimensional arrays (tensors) and suggest a new interpolation formula in which a -dimensional array is interpolated on the entries of some TT-cross (tensor train-cross). The total number of entries and the complexity of our interpolation algorithm depend on linearly, so the approach does not suffer from the curse of dimensionality. We also propose a TT-cross method for computation of -dimensional integrals and apply it to some examples with dimensionality in the range from up to and the relative accuracy of order . In all constructions we capitalize on the new tensor decomposition in the form of tensor trains (TT-decomposition). [Copyright &y& Elsevier]

Abstract: In this paper, we study two interesting variants of the classical bin packing problem, called Lazy Bin Covering (LBC) and Cardinality Constrained Maximum Resource Bin Packing (CCMRBP) problems. For the offline LBC problem, we first prove the approximation ratio of the First-Fit-Decreasing and First-Fit-Increasing algorithms, then present an APTAS. For the online LBC problem, we give a competitive analysis for the algorithms of Next-Fit, Worst-Fit, First-Fit, and a modified HARMONIC algorithm. The CCMRBP problem is a generalization of the Maximum Resource Bin Packing (MRBP) problem Boyar et al. (2006) . For this problem, we prove that its offline version is no harder to approximate than the offline MRBP problem. [Copyright &y& Elsevier]

Abstract: Given an underlying communication network represented as an edge-weighted graph , a source node , a set of destination nodes , and a capacity which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source to send data to all destination nodes, under the constraint that in each routing tree at most destination nodes are allowed to receive the data copies. The cost of the routing scheme is the sum of the costs of all individual routing trees therein. Improving on our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of , where denotes the best known approximation ratio for the Steiner minimum tree problem. Since is about at the writing of the paper, the ratio achieved by our new algorithm is less than . In comparison, the previously best ratio was . [Copyright &y& Elsevier]

Abstract: This paper discusses a new approach for displacement-based topology optimization of continuum. Topology optimization of continuum can be performed with the optimization of material distribution. This optimization problem will include a large number of design variables, and it may require a high computational cost, especially for computation of gradient components with respect to an objective function and determination of an appropriate updating increment. A conventional approximate optimization technique may not be effective for this problem because it is a very large-scale problem. From this viewpoint, a new optimization technique, which is based on a successive approximation algorithm, is proposed. The proposed method consists of two main processes: (1) a linear approximation for determination of an updating direction, and (2) a nonlinear approximation for determining a scale coefficient of the updating vector. The first approximation is performed using the perturbation-based finite element analysis, and the second approximation is performed using the Kriging Method. In order to investigate effectiveness of the proposed method, it is applied to some typical examples for topology optimization problem. From the numerical results, effectiveness and validity of the proposed method are discussed. [Copyright &y& Elsevier]

Abstract: The well-known problem of the longest common subsequence (LCS), of two strings of lengths and respectively, is -time solvable and is a classical distance measure for strings. Another well-studied string comparison measure is that of parameterized matching, where two equal-length strings are a parameterized match if there exists a bijection on the alphabets such that one string matches the other under the bijection. All works associated with parameterized pattern matching present polynomial time algorithms. There have been several attempts to accommodate parameterized matching along with other distance measures, as these turn out to be natural problems, e.g., Hamming distance, and a bounded version of edit-distance. Several algorithms have been proposed for these problems. In this paper we consider the longest common parameterized subsequence problem which combines the LCS measure with parameterized matching. We prove that the problem is -hard, and then show a couple of approximation algorithms for the problem. [Copyright &y& Elsevier]

Abstract: Let be a simple graph without isolated vertices. A vertex set is a paired-dominating set if every vertex in has a neighbor in and the induced subgraph has a perfect matching. In this paper, we investigate the approximation hardness of paired-domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given. [Copyright &y& Elsevier]

Abstract: This paper presents a simple procedure for obtaining a numerical approximation to the consistent tangent matrix, together with a straightforward implicit (Euler backward) integration algorithm. The combined algorithm is used to incorporate four models into the commercial finite element package ABAQUS/Standard; illustrating how it can be used to rapidly implement material models within finite element analysis. The models have been chosen, not only because they help to illuminate the structure of the algorithm, but also because they illustrate its wide ranging applicability and permit the procedure to be tested against analytical results and an existing, well established, model. [Copyright &y& Elsevier]

Abstract: In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into “rooms”, one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm. [Copyright &y& Elsevier]

Abstract: A trajectory is a sequence of locations, each associated with a timestamp, describing the movement of a point. Trajectory data is becoming increasingly available and the size of recorded trajectories is getting larger. In this paper we study the problem of compressing planar trajectories such that the most common spatio-temporal queries can still be answered approximately after the compression has taken place. In the process, we develop an implementation of the Douglas–Peucker path-simplification algorithm which works efficiently even in the case where the polygonal path given as input is allowed to self-intersect. For a polygonal path of size n, the processing time is for or depending on the type of simplification. [Copyright &y& Elsevier]

Abstract: This paper presents a novel quadratic optimal neural fuzzy control for synchronization of uncertain chaotic systems via approach. In the proposed algorithm, a self-constructing neural fuzzy network (SCNFN) is developed with both structure and parameter learning phases, so that the number of fuzzy rules and network parameters can be adaptively determined. Based on the SCNFN, an uncertainty observer is first introduced to watch compound system uncertainties. Subsequently, an optimal NFN-based controller is designed to overcome the effects of unstructured uncertainty and approximation error by integrating the NFN identifier, linear optimal control and approach as a whole. The adaptive tuning laws of network parameters are derived in the sense of quadratic stability technique and Lyapunov synthesis approach to ensure the network convergence and synchronization performance. The merits of the proposed control scheme are not only that the conservative estimation of NFN approximation error bound is avoided but also that a suitable-sized neural structure is found to sufficiently approximate the system uncertainties. Simulation results are provided to verify the effectiveness and robustness of the proposed control method. [Copyright &y& Elsevier]

Abstract: In this paper, an iterative algorithm is constructed to solve the minimum Frobenius norm residual problem: min over bisymmetric matrices. By this algorithm, for any initial bisymmetric matrix , a solution can be obtained in finite iteration steps in the absence of roundoff errors, and the solution with least norm can be obtained by choosing a special kind of initial matrix. Furthermore, in the solution set of the above problem, the unique optimal approximation solution to a given matrix in the Frobenius norm can be derived by finding the least norm bisymmetric solution of a new corresponding minimum Frobenius norm problem. Given numerical examples show that the iterative algorithm is quite effective in actual computation. [Copyright &y& Elsevier]

Abstract: By introducing a bivariate matrix-valued linear functional on the scalar polynomial space, a general two-dimensional (2-D) matrix Padé-type approximant () in the inner product space is defined in this paper. The coefficients of its denominator polynomials are determined by taking the direct inner product of matrices. The remainder formula is developed and an algorithm for the numerator polynomials is presented when the generating polynomials are given in advance. By means of the Hankel-like coefficient matrix, a determinantal expression of is presented. Moreover, to avoid the computation of the determinants, two efficient recursive algorithms are proposed. At the end the method of is applied to partial realization problems of 2-D linear systems. [Copyright &y& Elsevier]

Abstract: In this paper a new algorithm based on the reproducing kernel method is presented for linear transient analysis using very large time steps. In the conventional time integration methods, the required accuracy is always achieved by either decreasing the size of time steps or increasing the order of approximations. The proposed method, however, does not require a restriction on the size of the time step. The required approximating functions for integration of governing equations are determined using the concept of reproduction of the solution within each time step. A recurrence relationship is obtained through solving the governing equation by the point collocation based reproducing kernel method within the time step. In collocation points, the values of external excitation can be obtained either through the approximation between the values at the beginning and the end of each time step or assigning the exact values of the external force. Hence, one advantage of this new method is the independency of the sampling rates of external excitation from the size of the time step. The proposed method is applied for solving first and second order differential equations, and advantages of the method are illustrated through a number of numerical examples. [Copyright &y& Elsevier]

Abstract: In this paper, we present a new algorithm for computing local extrema by modifying and combining algorithms in symbolic and numerical computation. This new algorithm improves the classical steepest descent method that may not terminate, by combining a Sturm’s theorem based separation method and a sufficient condition on infeasibility. In addition, we incorporate a grid subdivision method into our algorithm to approximate all local extrema. The complexity of our algorithm is polynomial in a newly defined condition number, and singly exponential in the number of variables. [Copyright &y& Elsevier]

Abstract: This paper is concerned with a new algorithm for giving the analytical and approximate solutions of a class of boundary value problems in the reproducing kernel space. The analytical solution and approximate solution are represented in terms of series. For any initial function , we prove , , . Two numerical examples are studied to demonstrate the accuracy of the present method. Results obtained by the method indicate the method is simple and effective. [Copyright &y& Elsevier]

Abstract: In this paper, a novel learning strategy for radial basis function networks (RBFN) is proposed. By adjusting the parameters of the hidden layer, including the RBF centers and widths, the weights of the output layer are adapted by local optimization methods. A new local optimization algorithm based on a combination of the gradient and Newton methods is introduced. The efficiency of some local optimization methods to update the weights of RBFN is studied in solving systems of nonlinear integral equations. [Copyright &y& Elsevier]

Abstract: In transfer learning the aim is to solve new learning tasks using fewer examples by using information gained from solving related tasks. Existing transfer learning methods have been used successfully in practice and PAC analysis of these methods have been developed. But the key notion of relatedness between tasks has not yet been defined clearly, which makes it difficult to understand, let alone answer, questions that naturally arise in the context of transfer, such as, how much information to transfer, whether to transfer information, and how to transfer information across tasks. In this paper, we look at transfer learning from the perspective of Algorithmic Information Theory/Kolmogorov complexity theory, and formally solve these problems in the same sense Solomonoff Induction solves the problem of inductive inference. We define universal measures of relatedness between tasks, and use these measures to develop universally optimal Bayesian transfer learning methods. We also derive results in AIT that are interesting by themselves. To address a concern that arises from the theory, we also briefly look at the notion of Kolmogorov complexity of probability measures. Finally, we present a simple practical approximation to the theory to do transfer learning and show that even these are quite effective, allowing us to transfer across tasks that are superficially unrelated. The latter is an experimental feat which has not been achieved before, and thus shows the theory is also useful in constructing practical transfer algorithms. [Copyright &y& Elsevier]

Abstract: This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm that achieves an expected ratio of for any constant . By modifying their algorithm, we obtain a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio of for any constant . [Copyright &y& Elsevier]

Abstract: For a fixed family of graphs, an -packing in a graph is a set of pairwise vertex-disjoint subgraphs of , each isomorphic to an element of . Finding an -packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just . In this paper we provide new approximation algorithms and hardness results for the -packing problem where . We show that already for the -packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed . For we obtain better approximations. For we obtain a simple -approximation, achieving a known ratio that follows from a more involved algorithm of Halldórsson. For , we obtain a -approximation, and for we obtain a -approximation. [Copyright &y& Elsevier]

Abstract: In generalized tree alignment problem, we are given a set of biologically related sequences and we are interested in a minimum cost evolutionary tree for . In many instances of this problem partial phylogenetic tree for is known. In such instances, we would like to make use of this knowledge to restrict the tree topologies that we consider and construct a biologically relevant minimum cost evolutionary tree. So, we propose the following natural generalization of the generalized tree alignment problem, a problem known to be MAX-SNP Hard, stated as follows: Constrained Generalized Tree Alignment Problem [S. Divakaran, Algorithms and heuristics for constrained generalized alignment problem, DIMACS Technical Report 2007-21, 2007]: Given a set of related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of needs to satisfy, construct a minimum cost evolutionary tree for . In this paper, we present constant approximation algorithms for the constrained generalized tree alignment problem. For the generalized tree alignment problem, a special case of this problem, our algorithms provide a guaranteed error bound of . [Copyright &y& Elsevier]

Abstract: This paper presents an algorithm for approximating arbitrary polygonal meshes with subdivision surfaces, with the objective of preserving the relevant features of the object while searching the coarsest possible control mesh. The main idea is to firstly extract the feature lines of the object, and secondly construct the subdivision surface over this network. Control points are created by approximating these lines while the connectivity is built with respect to the anisotropy of the object. Our algorithm reinforces the similarity between the subdivision surface and the original shape by affecting an integer sharpness degree to each control edge in order to accurately reproduce the different curvature radii of corresponding fillets and blends. [Copyright &y& Elsevier]

Abstract: We investigate the group key management problem for broadcasting applications. Previous work showed that, in handling key updates, batch rekeying can be more cost effective than individual rekeying. One model for batch rekeying is to assume that every user has probability of being replaced by a new user during a batch period with the total number of users unchanged. Under this model, it was recently shown that an optimal key tree can be constructed in linear time when is a constant and in time when . In this paper, we investigate more efficient algorithms for the case , i.e., when membership changes are sparse. We design an heuristic algorithm for the sparse case and show that it produces a nearly 2-approximation to the optimal key tree. Simulation results show that its performance is even better in practice. We also design a refined heuristic algorithm and show that it achieves an approximation ratio of for any fixed and , as . Finally, we give another approximation algorithm for any which is shown to be quite good by our simulations. [Copyright &y& Elsevier]

Abstract: Given a set of elements, a family of subsets of , and a connected graph on vertex set ,a connected set cover (CSC) is a subfamily of such that every element in is covered by at least one set of , and the subgraph of induced by is connected. If furthermore is -connected and every element in is covered by at least sets in , then is a -CSC. In this paper, we present two approximation algorithms for the minimum CSC problem, and one approximation algorithm for the minimum -CSC problem. Performance ratios are analyzed. These are the first approximation algorithms for CSC problems in general graphs with guaranteed performance ratios. [Copyright &y& Elsevier]