Search

Abstract: This paper continues the theme of the recent work Chen et al. (2008) , in which fast collocation methods are introduced for solving ill-posed Fredholm integral equations of the first kind. We develop in this paper multilevel augmentation algorithms, which lead to fast solutions of the discrete equations resulting from fast collocation methods. Regularization parameter choice strategies are given for proposed methods. The theoretical analysis and numerical experiments illustrate the accuracy and efficiency of the algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of underdetermined blind source separation (UBSS), i.e., there are more sources than mixtures. By exploiting the time–frequency (TF) sparsity of the source signals, some TF–UBSS algorithms have recently been proposed in the literature. These algorithms require that the number of active sources at any TF point should not exceed one or be strictly less than the number of mixtures. In this paper, we show that if the number of sources is greater than the number of mixtures by one, the sparsity assumption can be further relaxed. Especially, it is allowed to have as many sources as mixtures at any TF point in this case. Then we propose a new TF–UBSS method to recover the sources. The relaxation on the maximum number of active sources at TF points ensures that the TF-based methods can be used in a wider range of applications. [Copyright &y& Elsevier]

Infinitesimal perturbation analysis (IPA) provides formulas for random gradients (derivatives) of performance measures with respect to parameters of interest, computed from sample paths of stochastic systems. In practice, IPA derivatives may be computed either from simulation runs or from empirical field data (when the formulas are nonparametric). Nonparametric IPA derivatives in fluid-flow queues have been recently derived for the loss volume and time average of buffer occupancy, with respect to buffer size, and arrival-rate or service-rate parameters. Additionally, these IPA derivatives have been shown to be unbiased in the sense that their expectation and differentiation operators commute, while their traditional discrete counterparts have long been known to be generally biased. Recent work has further shown how to map the computation of IPA derivatives from a fluid-flow queue to a compatible discrete counterpart without an appreciable loss of accuracy in performance measures. Thus, this work holds the promise of potential applications of IPA derivatives to gradient-based optimization of objective functions involving performance metrics parameterized by settable parameters in a queueing network context. This paper is an empirical study of IPA derivatives of individual queues within queueing systems which model telecommunications networks and some of their protocols. As a testbed, we used HNS (Hybrid Network Simulator) — a hybrid Java simulator of queueing networks with traffic streams subject to several telecommunications protocols. More specifically, the hybrid feature of HNS admits models with mixtures of discrete (packet) flows and continuous (fluid) flows, and collects detailed statistics and IPA derivatives for all flow types. The paper outlines the mapping of IPA derivatives from the fluid domain to the packet domain as implemented in HNS, and studies the accuracy of IPA derivatives in compatible fluid and packet queueing models, as well as the stabilization of their values in time. Our experimental results lend empirical support to the contention that IPA derivatives can be accurately computed from discrete versions by adopting a fluid-flow view. Furthermore, the long-run values of various IPA derivatives are empirically shown to stabilize quite fast. Finally, the results provide the basis and motivation for IPA applications to the optimization of telecommunications network design and to potential new open-loop protocols that take advantage of IPA information. [Copyright &y& Elsevier]

Two symbolic algorithms for inverting k -tridiagonal matrices have been recently found by El-Mikkawy and Atlan (2014, 2015). These two algorithms are mainly based on the Doolittle LU factorization of the k -tridiagonal matrix. In the current paper, we present a new explicit analytic expression for the inverses of general tridiagonal matrices at first. By using a block diagonalization technique, we then relate k -tridiagonal matrix inversion to tridiagonal matrix inversion. Meanwhile, an efficient algorithm is derived for computing the inverses of nonsingular k -tridiagonal matrices with the help of any algorithm for computing the inverses of tridiagonal matrices. Three examples are given in order to illustrate the performance and efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

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: Data compression via the Huffman algorithm, which is a data compression technique, is the most efficient technique between single symbol data compression techniques. This algorithm is counted among statistical data compression techniques. Many efforts have been made for optimizing this technique and some algorithms have been presented, too. One of these algorithms is the ACW algorithm which is presented by Hussein Al-Bahadili et al. At first, they used the Huffman algorithm and then used the results of the Huffman algorithm as the input of their algorithm to calculate the optimum character wordlength. So, they decreased the stored characters via increasing the character wordlength for doing the compression. In this paper, we examined and criticized the ACW algorithm and presented some of its weaknesses via suitable counterexamples. At the end, it was concluded that the optimum character wordlength can never be calculated by extant techniques. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the computation problem of expansion coefficients of Melnikov functions for near-Hamiltonian systems with a nilpotent center. We develop a general method for finding the computation formulas for the expansion coefficients. Based on the new method, an efficient algorithm is established to systematically compute the coefficients. Moreover, as an application we consider a kind of Liénard systems with a nilpotent center and study the number of limit cycles near the center. [Copyright &y& Elsevier]

Abstract: Inspired by the paper on quantum knots and knot mosaics (Lomonaco and Kauffman, 2008 ) and grid diagrams (or arc presentations), used extensively in the computations of Heegaard–Floer knot homology (Bar-Natan, 0000 , Cromwell, 1995 , Manolescu et al., 2007 ), we construct the more concise representation of knot mosaics and grid diagrams via mirror-curves. Tame knot theory is equivalent to knot mosaics (Lomonaco and Kauffman, 2008 ), mirror-curves, and grid diagrams (Bar-Natan, 0000 , Cromwell, 1995 , Kuriya, 2008 , Manolescu et al., 2007 ). Hence, we introduce codes for mirror-curves treated as knot or link diagrams placed in rectangular square grids, suitable for software implementation. We provide tables of minimal mirror-curve codes for knots and links obtained from rectangular grids of size 3×3 and (), and describe an efficient algorithm for computing the Kauffman bracket and -polynomials (Jablan and Sazdanović, 2007 , Kauffman, 2006 , Kauffman, 1987 ) directly from mirror-curve representations. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the nonlinear second-order cone programming problem. By combining an SQP method and filter technique, we present a trust region SQP-filter method for solving this problem. The proposed algorithm avoids using the classical merit function with penalty term. Furthermore, under standard assumptions, we prove that the iterative sequence generated by the presented algorithm converges globally. Preliminary numerical results indicate that the algorithm is promising. [Copyright &y& Elsevier]

Abstract: Shortest hop or distance path is one of the most common methods used for relaying messages in a wide variety of networks. It provides an efficient message relaying to destination in terms of energy and time. There are many algorithms for constructing shortest hop or distance path. However, according to our knowledge, no algorithm for constructing a shortest hop multipath for wireless sensor networks (WSNs) has yet been proposed in the literature. In this paper, we propose a novel distributed shortest hop multipath algorithm for WSNs in order to generate energy efficient paths for data dissemination or routing. The proposed algorithm generates shortest hop braided multipath to be used for fault-tolerance or load-balancing. It guarantees the BFS tree and generates near optimal paths in message complexity and time complexity regarding the communication costs towards the sink after termination of algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, we present a dynamic programming (DP) algorithm for the multi-objective 0–1 knapsack problem (MKP) by combining two state reduction techniques. One generates a backward reduced-state DP space (BRDS) by discarding some states systematically and the other reduces further the number of states to be calculated in the BRDS using a property governing the objective relations between states. We derive the condition under which the BRDS is effective to the MKP based on the analysis of solution time and memory requirements. To the authors’ knowledge, the BRDS is applied for the first time for developing a DP algorithm. The numerical results obtained with different types of bi-objective instances show that the algorithm can find the Pareto frontier faster than the benchmark algorithm for the large size instances, for three of the four types of instances conducted in the computational experiments. The larger the size of the problem, the larger improvement over the benchmark algorithm. Also, the algorithm is more efficient for the harder types of bi-objective instances as compared with the benchmark algorithm. [Copyright &y& Elsevier]

Abstract: In this paper an attempt is made to extend some standard results in set theory on the basis of soft set relations. Antisymmetric relation and transitive closure of a soft set relation are introduced and an analogue of Warshall’s algorithm is proposed for calculating the transitive closure of a soft set relation. Ordering on a soft set is defined and some set theoretical results based on this are proved. [Copyright &y& Elsevier]

Abstract: Although there have been many researches on cluster analysis considering feature (or variable) weights, little effort has been made regarding sample weights in clustering. In practice, not every sample in a data set has the same importance in cluster analysis. Therefore, it is interesting to obtain the proper sample weights for clustering a data set. In this paper, we consider a probability distribution over a data set to represent its sample weights. We then apply the maximum entropy principle to automatically compute these sample weights for clustering. Such method can generate the sample-weighted versions of most clustering algorithms, such as -means, fuzzy -means (FCM) and expectation & maximization (EM), etc. The proposed sample-weighted clustering algorithms will be robust for data sets with noise and outliers. Furthermore, we also analyze the convergence properties of the proposed algorithms. This study also uses some numerical data and real data sets for demonstration and comparison. Experimental results and comparisons actually demonstrate that the proposed sample-weighted clustering algorithms are effective and robust clustering methods. [Copyright &y& Elsevier]

Abstract: We study an on-line machine covering problem, in which jobs arrive one by one and their processing times are known upon their arrival, and jobs are allowed to migrate between machines when a new job is added in the system. However, the total processing time of migration induced by an incoming job is bounded by a constant factor times the processing time of the incoming job. The objective is to maximize the minimum machine load. In this paper, we present an on-line algorithm with competitive ratio 6/5 for the two identical machines case with . Moreover, the presented on-line algorithm is only a local migration, that is, when one job is assigned to machine , only the jobs on machine are allowed to migrate. We also show that the provided algorithm is a best possible on-line algorithm in the sense of local migration. [Copyright &y& Elsevier]

Abstract: In this paper, a weight selection procedure in the --means algorithm is proposed based on the statistical variation viewpoint. This approach can solve the --means algorithm’s problem that the clustering quality is greatly affected by the initial value of weight. After the statistics of data, the weights of data are designed to provide more information for the character of --means algorithm so as to improve the precision. Furthermore, the corresponding computational complexity is analyzed as well. We compare the clustering results of the --means algorithm with the different initialization methods. Results from color image segmentation illustrate that the proposed procedure produces better segmentation than the random initialization according to Liu and Yang’s (1994) evaluation function. [Copyright &y& Elsevier]

Abstract: This paper explores the problems of generalized center conditions and integrability of resonant infinity for a complex polynomial differential system. The method is based on converting resonant infinity into an elementary singular point by a homeomorphic transformation. The calculation of generalized singular point quantities is an effective way of finding necessary conditions for integrable systems. A new recursive algorithm for computing generalized singular point quantities at the origin of the transformed system is derived. At the same time, a necessary and sufficient condition for resonant infinity to be a generalized complex center is presented. As an application of the new recursive algorithm, the generalized center conditions for resonant infinity for a class of cubic systems are discussed. To the best of our knowledge, this is the first time that the generalized center problem has been considered for resonant infinity. [Copyright &y& Elsevier]

Abstract: Nonlinear differential equations with fractional derivatives give general representations of real life phenomena. In this paper, a modification of the differential transform method (DTM) for solving the nonlinear fractional differential equation is introduced for the first time. The new algorithm is simple and gives an accurate solution. Moreover the new solution is continuous and analytic on each subinterval. A fractional Chen system is considered, to demonstrate the efficiency of the algorithm. The results obtained show good agreement with the generalized Adams–Bashforth–Moulton method. [Copyright &y& Elsevier]

Abstract: A novel modified differential evolution algorithm (NMDE) is proposed to solve constrained optimization problems in this paper. The NMDE algorithm modifies scale factor and crossover rate using an adaptive strategy. For any solution, if it is at a standstill, its own scale factor and crossover rate will be adjusted in terms of the information of all successful solutions. We can obtain satisfactory feasible solutions for constrained optimization problems by combining the NMDE algorithm and a common penalty function method. Experimental results show that the proposed algorithm can yield better solutions than those reported in the literature for most problems, and it can be an efficient alternative to solving constrained optimization problems. [Copyright &y& Elsevier]

Abstract: This paper presents algorithms for decomposing any zero-dimensional polynomial set into simple sets over an arbitrary finite field, with an associated ideal or zero decomposition. As a key ingredient of these algorithms, we generalize the squarefree decomposition approach for univariate polynomials over a finite field to that over the field product determined by a simple set. As a subprocedure of the generalized squarefree decomposition approach, a method is proposed to extract the th root of any element in the field product. Experiments with a preliminary implementation show the effectiveness of our algorithms. [Copyright &y& Elsevier]

Abstract: Richardson Extrapolation is a powerful computational tool which can successfully be used in the efforts to improve the accuracy of the approximate solutions of systems of ordinary differential equations (ODEs) obtained by different numerical methods (including here combined numerical methods consisting of appropriately chosen splitting procedures and classical numerical methods). Some stability results related to two implementations of the Richardson Extrapolation (Active Richardson Extrapolation and Passive Richardson Extrapolation) are formulated and proved in this paper. An advanced atmospheric chemistry scheme, which is commonly used in many well-known operational environmental models, is applied in a long sequence of experiments in order to demonstrate the fact that [(a)] it is indeed possible to improve the accuracy of the numerical results when the Richardson Extrapolation is used (also when very difficult, badly scaled and stiff non-linear systems of ODEs are to be treated), [(b)] the computations can become unstable when the combination of the Trapezoidal Rule and the Active Richardson Extrapolation is used, [(c)] the application of the Active Richardson Extrapolation with the Backward Euler Formula is leading to a stable computational process, [(d)] experiments with different algorithms for solving linear systems of algebraic equations are very useful in the efforts to select the most suitable approach for the particular problems solved and [(e)] the computational cost of the Richardson Extrapolation is much less than that of the underlying numerical method when a prescribed accuracy has to be achieved. [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: In this paper, we study an implicit iterative algorithm for two nonexpansive mappings and two finite families of nonexpansive mappings in Banach spaces. We prove some weak and strong convergence theorems for these iterative algorithms. Our results extend some existing results. [Copyright &y& Elsevier]

Abstract: The recently published edge- and lookup table-based inverse halftoning (ELIH) algorithm has shown its quality and superiority when compared with the previous lookup table-based IH algorithm. This paper presents a new finite state machine model (FSMM)-based search method to speed up the existing ELIH algorithm significantly while preserving the same image quality as in the ELIH algorithm. From the observation that the sliding window for the ELIH algorithm moves from left to right one position; there are therefore one output column and one input column which are introduced at each step and thus a simple finite state machine can track the transitions from the current window movement to the next. This is faster than a full search in the lookup table. Under thirty typical testing images adopted from Meşe’s website, experimental results demonstrated that the proposed FSMM-based ELIH algorithm has an improvement in execution time of 20% to 80%, with a typical improvement of 50%, when compared to the ELIH algorithm. [Copyright &y& Elsevier]

The paper explores a trust-region active-set algorithm for general nonlinear optimization with nonlinear equality and inequality constraints. In this algorithm, an active-set strategy is used together with trust-region methods to compute the trial step. penalty functions are employed to obtain the global convergence. The global convergence of this algorithm is proved under standard conditions. The numerical tests show the efficiency of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: Population initialization is a crucial task in evolutionary algorithms because it can affect the convergence speed and also the quality of the final solution. If no information about the solution is available, then random initialization is the most commonly used method to generate candidate solutions (initial population). This paper proposes a novel initialization approach which employs opposition-based learning to generate initial population. The conducted experiments over a comprehensive set of benchmark functions demonstrate that replacing the random initialization with the opposition-based population initialization can accelerate convergence speed. [Copyright &y& Elsevier]

This paper details an efficient algorithm for particles undergoing random walks in the presence of complex, two-dimensional, solid boundaries. The scheme is developed for the simulation of vortex diffusion using the random vortex method. Both vortex blobs and sheets are handled. The relevant modifications for using the algorithm with the vorticity redistribution technique are also discussed. The algorithm is designed to be used in the framework of an existing fast multipole implementation. A measure for the geometric complexity of a body is introduced and the algorithm’s efficiency is studied as various parameters are changed for bodies of varying complexity. [Copyright &y& Elsevier]

Abstract: This paper concentrates on a limited-flow network in which each node and branch has a designated capacity, which will have different lower levels due to various partial and complete failures. We try to evaluate the system unreliability that the maximum flow of the network is less than or equal to the demand d without exceeding the budget B. First, a simple algorithm in terms of minimal cuts is proposed to generate all (d, B)-MCs in order to evaluate the system unreliability. A computer example is shown to illustrate the solution procedure. [Copyright &y& Elsevier]

Abstract: Recently, circulant graphs have received a lot of attention; and a new method was proposed for designing fault-tolerant solutions for any given circulant graph. This method works by partitioning the offsets of the graph in many ways; each leads to one or more solutions. By comparing all these solutions, we can find the one with the least node-degree. In this paper, we shall first review this method; and then re-examine its applications to the design of k-fault-tolerant meshes (for all possible values of k). Our results demonstrate that the solutions obtained (for both two and three-dimensional meshes) are efficient. [Copyright &y& Elsevier]

Abstract: We consider a multiserver retrial queueing model with applications in service industries, in which customers arrive according to a Markovian arrival process (MAP). Any admitted customer either [(a)] gets service and leaves the system as a satisfied primary customer; or [(b)] gets service and becomes a secondary customer. The secondary customers leave the system either as satisfied or unsatisfied with their services. In this paper, we perform the steady state analysis of the model and also study the algorithmic aspects of this queueing model including an optimization problem. [Copyright &y& Elsevier]

Abstract: In this paper, a kind of nonlinear optimization problems with nonlinear inequality constraints are discussed, and a new SQP feasible descent algorithm for solving the problems is presented. At each iteration of the new algorithm, a convex quadratic program (QP) which always has feasible solution is solved and a master direction is obtained, then, an improved (feasible descent) direction is yielded by updating the master direction with an explicit formula, and in order to avoid the Maratos effect, a height-order correction direction is computed by another explicit formula of the master direction and the improved direction. The new algorithm is proved to be globally convergent and superlinearly convergent under mild conditions without the strict complementarity. Furthermore, the quadratic convergence rate of the algorithm is obtained when the twice derivatives of the objective function and constrained functions are adopted. Finally, some numerical tests are reported. [Copyright &y& Elsevier]

Abstract: System reliability evaluation for flow networks is an important issue in our modern society. This paper studies the system reliability that a given amount of multicommodity can be transmitted through a stochastic-flow network, in which each are has several capacities, under the cost constraint. A simple algorithm is proposed to generate all (d 1, d 2,…, d p ; C)-MPs where d i is the demand of commodity i. The system reliability can then be calculated in terms of (d 1, d 2,…, d p ; C)-MPs. [Copyright &y& Elsevier]

Abstract: In this paper, some new oscillation criteria are obtained for the first-order delay difference equation , where k,l1,l2,, ls are positive integer numbers, f is a function. Our results improve the known results in the literature. And some examples are given to demonstrate the advantage of our results. [Copyright &y& Elsevier]

Abstract: The scheduling problems studied in this paper concern the two-stage no-wait flowshops with parallel machines under the objective function of the minimization of the maximum completion time. A new heuristic algorithm, i.e., the minimum deviation algorithm, is developed to solve the problems. In order to evaluate the average case performance of the algorithm, we design numerical experiments to compare the effectiveness of the algorithm with that of the other approximation algorithms. Extensive simulations are conducted under different shop conditions, and the results statistically show that the minimum deviation algorithm performs well under most of the situations. [Copyright &y& Elsevier]

The optimization versions of the k-PARTITIONING problems are considered in this paper. For the objective to maximize the minimum load of m subsets, we first show that the FOLDING algorithm has a tight worst case ratio of max{2/k,1/m}. Then, we present an algorithm called HARMONIC1 with a worst case ratio at least max{ 1/k, 1/(⌈Σi=1m 1/i ⌉ +1)}. It concludes the HARMONIC1 is better than FOLDING for k > 2(⌈ Σi=1m 1/i ⌉ + 1). We further show that HARMONICI is asymptotically optimal ordinal algorithm. We also present an algorithm HARMONIC2 for solving the general κi-PARTITIONING problem. [Copyright &y& Elsevier]

Let CSRnxn={A=(aij)∊Rnxn|aij=an+1−j, i,j=1,2…, n} In this paper, we mainly discuss solving the following problems. PROBLEM Io Given X, B ∊ Rnxm Find A ∊ CSRn×n such that AX = B. PROBLEM I. Given X, B ∊ Rn×m. Find A ∊ CSRn×n such that ∥AX−B∥=min.PROBLEM II. Given A` ∊ Rn×n. Find A* ∊ SE such that where ∥ · ∥ is the Frobenius norm, and SE is the solution set of Problem I or I0.The expressions of the general solution of Problems I and 10 have been derived. The sufficient and necessary conditions for the solvability of Problem I0 have been provided. The numerical algorithm to find the optimal approximate solution and some numerical experiments have been given. [Copyright &y& Elsevier]

In this paper, we combine the new trust region subproblem proposed in [1] with the nonmonotone technique to propose a new algorithm for unconstrained optimization—the nonmonotone adaptive trust region method. The local and global convergence properties of the nonmonotone adaptive trust region method are proved. Its efficiency is tested by numerical results. [Copyright &y& Elsevier]