Search

In this paper we study the bounded perturbation resilience of the extragradient and the subgradient extragradient methods for solving a variational inequality (VI) problem in real Hilbert spaces. This is an important property of algorithms which guarantees the convergence of the scheme under summable errors, meaning that an inexact version of the methods can also be considered. Moreover, once an algorithm is proved to be bounded perturbation resilience, superiorization can be used, and this allows flexibility in choosing the bounded perturbations in order to obtain a superior solution, as well explained in the paper. We also discuss some inertial extragradient methods. Under mild and standard assumptions of monotonicity and Lipschitz continuity of the VI's associated mapping, convergence of the perturbed extragradient and subgradient extragradient methods is proved. In addition we show that the perturbed algorithms converge at the rate of $O(1/t)$ . Numerical illustrations are given to demonstrate the performances of the algorithms. [ABSTRACT FROM AUTHOR]

This paper is concerned with mathematical and numerical analysis of the system of radiative integral transfer equations. The existence and uniqueness of solution to the integral system is proved by establishing the boundedness of the radiative integral operators and proving the invertibility of the operator matrix associated with the system. A collocation-boundary element method is developed to discretize the differential-integral system. For the non-convex geometries, an element-subdivision algorithm is developed to handle the computation of the integrals containing the visibility factor. An efficient iterative algorithm is proposed to solve the nonlinear discrete system and its convergence is also established. Numerical experiment results are also presented to verify the effectiveness and accuracy of the proposed method and algorithm. [ABSTRACT FROM AUTHOR]

In this paper, two arctangent-based normalized subband adaptive filter (Arc-NSAF) algorithms are proposed, which are derived from two different forms of arctangent cost function and their difference is the order of the arctangent computation and the summation operation of the normalized subband error signal. Benefiting from the excellent property of the arctangent function for suppressing impulsive interferences, the proposed Arc-NSAF algorithms not only possess good robustness against impulsive interferences, but also obtain faster convergence rate for the colored input signals. To further improve the convergence performance of the Arc-NSAFs when identifying sparse system, the proportionate versions of the Arc-NSAF algorithms are also proposed. Simulation results have demonstrated the superiority of the proposed algorithms in impulsive interferences environments as compared to their respective competitors. [ABSTRACT FROM AUTHOR]

Scheduling of jobs and resources on a shop floor is an ever green optimization problem. Job shop scheduling problem (JSSP) is an allocation of 'n' jobs on 'm' machines so as to complete processing of all jobs in a minimum possible time. The JSSP has been addressed by various direct, indirect methods, programs, and algorithms in the last 40 year of literature. This paper presents a new paradigm of invasive weed optimization which mimics the process of weed colonization and distribution to solve JSSPs. The algorithm had shown encouraging and promising outputs on standard benchmarking problems. [ABSTRACT FROM AUTHOR]

Matrix-Matrix Multiplication (MMM) is a highly important kernel in linear algebra algorithms and the performance of its implementations depends on the memory utilization and data locality. There are MMM algorithms, such as standard, Strassen-Winograd variant, and many recursive array layouts, such as Z-Morton or U-Morton. However, their data locality is lower than that of the proposed methodology. Moreover, several SOA (state of the art) self-tuning libraries exist, such as ATLAS for MMM algorithm, which tests many MMM implementations. During the installation of ATLAS, on the one hand an extremely complex empirical tuning step is required, and on the other hand a large number of compiler options are used, both of which are not included in the scope of this paper. In this paper, a new methodology using the standard MMM algorithm is presented, achieving improved performance by focusing on data locality (both temporal and spatial). This methodology finds the scheduling which conforms with the optimum memory management. Compared with (Chatterjee et al. in IEEE Trans. Parallel Distrib. Syst. 13:1105, ; Li and Garzaran in Proc. of Lang. Compil. Parallel Comput., ; Bilmes et al. in Proc. of the 11th ACM Int. Conf. Super-comput., ; Aberdeen and Baxter in Concurr. Comput. Pract. Exp. 13:103, ), the proposed methodology has two major advantages. Firstly, the scheduling used for the tile level is different from the element level's one, having better data locality, suited to the sizes of memory hierarchy. Secondly, its exploration time is short, because it searches only for the number of the level of tiling used, and between (1, 2) (Sect. 4) for finding the best tile size for each cache level. A software tool (C-code) implementing the above methodology was developed, having the hardware model and the matrix sizes as input. This methodology has better performance against others at a wide range of architectures. Compared with the best existing related work, which we implemented, better performance up to 55% than the Standard MMM algorithm and up to 35% than Strassen's is observed, both under recursive data array layouts. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm to compute the law of the Lie algebra $\mathfrak{g}_{n}$ associated with the Lie group G, formed of all the n× n upper-unitriangular matrices. The goal of this paper is to show the algorithm that computes the law of $\mathfrak{g}_{n}$ and its implementation using the symbolic computation package MAPLE. In addition, the complexity of the algorithm is described. [ABSTRACT FROM AUTHOR]

Surface multiresolution processing is an important subject in CAGD. It also poses many challenging problems including the design of multiresolution algorithms. Unlike images which are in general sampled on a regular square or hexagonal lattice, the meshes in surfaces processing could have an arbitrary topology, namely, they consist of not only regular vertices but also extraordinary vertices, which requires the multiresolution algorithms have high symmetry. With the idea of lifting scheme, Bertram (Computing 72(1-2):29-39, ) introduces a novel triangle surface multiresolution algorithm which works for both regular and extraordinary vertices. This method is also successfully used to develop multiresolution algorithms for quad surface and $\sqrt 3$ triangle surface processing in Wang et al. (Vis Comput 22(9-11):874-884, ; IEEE Trans Vis Comput Graph 13(5):914-925, ) respectively. When considering the biorthogonality, these papers do not use the conventional $L^2({{\rm I}\kern-.2em{\rm R}}^2)$ inner product, and they do not consider the corresponding lowpass filter, highpass filters, scaling function and wavelets. Hence, some basic properties such as smoothness and approximation power of the scaling functions and wavelets for regular vertices are unclear. On the other hand, the symmetry of subdivision masks (namely, the lowpass filters of filter banks) for surface subdivision is well studied, while the symmetry of the highpass filters for surface processing is rarely considered in the literature. In this paper we introduce the notion of 4-fold symmetry for biorthogonal filter banks. We demonstrate that 4-fold symmetric filter banks result in multiresolution algorithms with the required symmetry for quad surface processing. In addition, we provide 4-fold symmetric biorthogonal FIR filter banks and construct the associated wavelets, with both the dyadic and $\sqrt 2$ refinements. Furthermore, we show that some filter banks constructed in this paper result in very simple multiresolution decomposition and reconstruction algorithms as those in Bertram (Computing 72(1-2):29-39, ) and Wang et al. (Vis Comput 22(9-11):874-884, ; IEEE Trans Vis Comput Graph 13(5):914-925, ). Our method can provide the filter banks corresponding to the multiresolution algorithms in Wang et al. (Vis Comput 22(9-11):874-884, ) for dyadic multiresolution quad surface processing. Therefore, the properties of the scaling functions and wavelets corresponding to those algorithms can be obtained by analyzing the corresponding filter banks. [ABSTRACT FROM AUTHOR]

This paper presents a numerical compression strategy for the boundary integral equation of acoustic scattering in two dimensions. These equations have oscillatory kernels that we represent in a basis of wave atoms, and compress by thresholding the small coefficients to zero. This phenomenon was perhaps first observed in 1993 by Bradie, Coifman, and Grossman, in the context of local Fourier bases (Bradie et al. in Appl. Comput. Harmon. Anal. 1:94–99, ). Their results have since then been extended in various ways. The purpose of this paper is to bridge a theoretical gap and prove that a well-chosen fixed expansion, the non-standard wave atom form, provides a compression of the acoustic single- and double-layer potentials with wave number k as O( k)-by- O( k) matrices with C ε δ k1+ δ non-negligible entries, with δ>0 arbitrarily small, and ε the desired accuracy. The argument assumes smooth, separated, and not necessarily convex scatterers in two dimensions. The essential features of wave atoms that allow this result to be written as a theorem are a sharp time-frequency localization that wavelet packets do not obey, and a parabolic scaling (wavelength of the wave packet) ∼ (essential diameter)2. Numerical experiments support the estimate and show that this wave atom representation may be of interest for applications where the same scattering problem needs to be solved for many boundary conditions, for example, the computation of radar cross sections. [ABSTRACT FROM AUTHOR]

In this paper, exact algorithms for solving the simple assembly line balancing type I problem are presented. The proposed algorithms consist of a constructive and two destructive algorithms. Several well-known lower-bound computational methods are also applied in these algorithms. Computational experiments were carried out to test the performance of the proposed algorithms based on a set of benchmark problem instances. The computational results show that the algorithms proposed in this paper are efficient in solving the simple assembly line balancing benchmark problem instances. Moreover, a problem instance whose optimal solution had previously been unknown is solved by one of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Given an undirected graph and a weighting function defined on the vertex set, the minimum weight vertex cover problem is to find a vertex subset whose total weight is minimum subject to the premise that the selected vertices cover all edges in the graph. In this paper, we introduce a meta-heuristic based upon the Ant Colony Optimization (ACO) approach, to find approximate solutions to the minimum weight vertex cover problem. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. A solution to the minimum weight vertex cover problem however needs not to constitute a path. The ACO algorithm proposed in this paper incorporates several new features so as to select vertices out of the vertex set whereas the total weight can be minimized as much as possible. Computational experiments are designed and conducted to study the performance of our proposed approach. Numerical results evince that the ACO algorithm demonstrates significant effectiveness and robustness in solving the minimum weight vertex cover problem. [ABSTRACT FROM AUTHOR]

This paper presents the design and preliminary evaluation of hierarchical partitioning and load-balancing techniques for distributed structured adaptive mesh refinement (SAMR) applications. The overall goal of these techniques is to enable the load distribution to reflect the state of the adaptive grid hierarchy and exploit it to reduce synchronization requirements, improve load-balance, and enable concurrent communications and incremental redistribution. The hierarchical partitioning algorithm (HPA) partitions the computational domain into subdomains and assigns them to hierarchical processor groups. Two variants of HPA are presented in this paper. The static hierarchical partitioning algorithm (SHPA) assigns portions of overall load to processor groups. In SHPA, the group size and the number of processors in each group is setup during initialization and remains unchanged during application execution. It is experimentally shown that SHPA reduces communication costs as compared to the Non-HPA scheme, and reduces overall application execution time by up to 59%. The adaptive hierarchical partitioning algorithm (AHPA) dynamically partitions the processor pool into hierarchical groups that match the structure of the adaptive grid hierarchy. Initial evaluations of AHPA show that it can reduce communication costs by up to 70%. [ABSTRACT FROM AUTHOR]

In this paper, we first propose a weak convergence algorithm, called the linesearch algorithm, for solving a split equilibrium problem and nonexpansive mapping (SEPNM) in real Hilbert spaces, in which the first bifunction is pseudomonotone with respect to its solution set, the second bifunction is monotone, and fixed point mappings are nonexpansive. In this algorithm, we combine the extragradient method incorporated with the Armijo linesearch rule for solving equilibrium problems and the Mann method for finding a fixed point of an nonexpansive mapping. We then combine the proposed algorithm with hybrid cutting technique to get a strong convergence algorithm for SEPNM. Special cases of these algorithms are also given. [ABSTRACT FROM AUTHOR]

The purpose of the paper is to study the proximal split feasibility problems. For solving the problems, we present new self-adaptive algorithms with the regularization technique. By using these algorithms, we give some strong convergence theorems for the proximal split feasibility problems. [ABSTRACT FROM AUTHOR]

This paper proposes a local intensity distribution equalization (LIDE) method for image enhancement. LIDE applies the idea of histogram equalization to parametric model in order to enhance an image using local information. It reduces the amount of computational resources required by traditional method like the adaptive histogram equalization, but allows enhancing detail similar to the latter technique. Integral image was used to efficiently estimate local statistics needed by the parametric model. This data structure drastically reduces the computational cost especially for megapixel image where a large local window is preferred. It should be noted that, with a large local window, the intensity distribution could contain multiple peaks. LIDE can nicely handle such complex distribution via mixture of parametric models. To speed-up the mixture parameter estimation, we propose an EM algorithm that is also based on the integral image data structure. Experimental results show that LIDE produces an enhanced image with greater detail and lower noise compared to several existing methods. [ABSTRACT FROM AUTHOR]

This paper presents a method to find all intersections between curved lines such as structural line elements and finite element meshes with intentions to generate smaller, non-compatible, line cells (e.g. bar elements) between crossings. The intersection finding algorithm works for two and three-dimensional meshes constituted by linear, quadratic or higher order elements. Using the proposed algorithm, meshes can then be automatically prepared for finite element analyses with techniques for embedding elements within others or analyses that require lines within solids. The application of the method is demonstrated by a number of numerical examples illustrating its capabilities in handling complex geometries, relative speed and convenience. [ABSTRACT FROM AUTHOR]

This paper analyzes the routing problem in order to design automatic train operation in a station. The authors consider the routing problem for the receipt-departure of trains and their shunting movements. It is noted that, in the case of stations with a branched track infrastructure, the number of all admissible routes becomes large, leading to bulky computations in the search procedure. A certain method is proposed to partition stations into zones for reducing the amount of computations. And finally, the authors pose the graph cutting problem of a railway station network with due account of track infrastructure features and present its solution algorithm. [ABSTRACT FROM AUTHOR]

The split variational inclusion problem is an important problem, and it is a generalization of the split feasibility problem. In this paper, we present a descent-conjugate gradient algorithm for the split variational inclusion problems in Hilbert spaces. Next, a strong convergence theorem of the proposed algorithm is proved under suitable conditions. As an application, we give a new strong convergence theorem for the split feasibility problem in Hilbert spaces. Finally, we give numerical results for split variational inclusion problems to demonstrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Consider a data set of vector-valued observations that consists of noisy inliers, which are explained well by a low-dimensional subspace, along with some number of outliers. This work describes a convex optimization problem, called reaper, that can reliably fit a low-dimensional model to this type of data. This approach parameterizes linear subspaces using orthogonal projectors and uses a relaxation of the set of orthogonal projectors to reach the convex formulation. The paper provides an efficient algorithm for solving the reaper problem, and it documents numerical experiments that confirm that reaper can dependably find linear structure in synthetic and natural data. In addition, when the inliers lie near a low-dimensional subspace, there is a rigorous theory that describes when reaper can approximate this subspace. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study a triple hierarchical variational inequality (THVI) with constraints of minimization and equilibrium problems. More precisely, let Fix(T) be the fixed point set of a nonexpansive mapping, let MEP(Θ,ϕ) be the solution set of a mixed equilibrium problem (MEP), and let Γ be the solution set of a minimization problem (MP) for a convex and continuously Frechet differential functional in Hilbert spaces. We want to find a solution x* ∈ Fix(T) ∩ MEP(Θ,ϕ) ∩ Γ of a variational inequality with a variational inequality constraint over the intersection of Fix(T), MEP(Θ,ϕ), and Γ . We propose a hybrid iterative algorithm with regularization to compute approximate solutions of the THVI, and we present the convergence analysis of the proposed iterative algorithm. [ABSTRACT FROM AUTHOR]

Let H1, H2 be real Hilbert spaces, C ⊆ H1 be a nonempty closed convex set, and 0 ∉ C. Let A : H1 → H2, B : H1 → H2 be two bounded linear operators. We consider the problem to find x ∈ C such that Ax = -Bx (0 = Ax + Bx). Recently, Eckstein and Svaiter presented some splitting methods for finding a zero of the sum of monotone operator A and B. However, the algorithms are largely dependent on the maximal monotonicity of A and B. In this paper, we describe some algorithms for finding a zero of the sum of A and B which ignore the conditions of the maximal monotonicity of A and B. [ABSTRACT FROM AUTHOR]

In this paper we offer an efficient controller synthesis algorithm for assume-guarantee specifications of the form $$\varphi _1 \wedge \varphi _2 \wedge \cdots \wedge \varphi _n \rightarrow \psi _1 \wedge \psi _2 \wedge \cdots \wedge \psi _m$$ . Here, $$\{\varphi _i,\psi _j\}$$ are all safety-MTL $$_{0, \infty }$$ properties, where the sub-formulas $$\{\varphi _i\}$$ are supposed to specify assumptions of the environment and the sub-formulas $$\{\psi _j\}$$ are specifying requirements to be guaranteed by the controller. Our synthesis method exploits the engine of Uppaal-Tiga and the novel translation of safety- and co-safety-MTL $$_{0, \infty }$$ properties into under-approximating, deterministic timed automata. Our approach avoids determinization of Büchi automata, which is the main obstacle for the practical applicability of controller synthesis for linear-time specifications. The experiments demonstrate that the chosen specification formalism is expressive enough to specify complex behaviors. The proposed approach is sound but not complete. However, it successfully produced solutions for all the experiments. Additionally we compared our tool with Acacia+ and Unbeast, state-of-the-art LTL synthesis tools; and our tool demonstrated better timing results, when we applied both tools to the analogous specifications. [ABSTRACT FROM AUTHOR]

Compressed sensing ensures the accurate reconstruction of sparse signals from far fewer samples than required in the classical Shannon-Nyquist theorem. In this paper, a generalized hard thresholding pursuit (GHTP) algorithm is presented that can recover unknown vectors without the sparsity level information. We also analyze the convergence of the proposed algorithm. Numerical experiments are given for synthetic and real-world data to illustrate the validity and the good performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Community detection is of considerable importance for understanding both the structure and function of complex networks. In this paper, we introduced the general procedure of the community detection algorithms using global and local structural information, where the edge betweenness and the local similarity measures respectively based on local random walk dynamics and local cyclic structures were used. The algorithms were tested on artificial and real-world networks. The results clearly show that all the algorithms have excellent performance in the tests and the local similarity measure based on local random walk dynamics is superior to that based on local cyclic structures. [ABSTRACT FROM AUTHOR]

The second Zagreb index of a graph G is an adjacency-based topological index, which is defined as Σuv∊E(G)(d(u)d(v)), where uv is an edge of G, d(u) is the degree of vertex u in G. In this paper, we consider the second Zagreb index for bipartite graphs. Firstly, we present a new definition of ordered bipartite graphs, and then give a necessary condition for a bipartite graph to attain the maximal value of the second Zagreb index. We also present an algorithm for transforming a bipartite graph to an ordered bipartite graph, which can be done in O(n2+n21) time for a bipartite graph B with a partition ∣X∣ = n1 and ∣Y∣ = n2. [ABSTRACT FROM AUTHOR]

This paper presents a novel hierarchical least squares algorithm for a class of non-uniformly sampled systems. Based on the hierarchical identification principle, the identification model with a high dimensional parameter vector is decomposed into a group of submodels with lower dimensional parameter vectors. By using the least squares method to identify the submodels and taking a coordinated measure to address the associated items between the submodels, all the system parameters can be estimated. The proposed algorithm can save the computation cost. The performance analysis indicates that parameter estimates converge to their true values. The simulation tests confirm the convergence results. [ABSTRACT FROM AUTHOR]

Variational models for image segmentation are usually solved by the level set method, which is not only slow to compute but also dependent on initialization strongly. Recently, fuzzy region competition models or globally convex segmentation models have been introduced. They are insensitive to initialization, but contain TV-regularizers, making them difficult to compute. Goldstein, Bresson and Osher have applied the split Bregman iteration to globally convex segmentation models which avoided the regularization of TV norm and speeded up the computation. However, the split Bregman method needs to solve a partial differential equation (PDE) in each iteration. In this paper, we present a simple algorithm without solving the PDEs proposed originally by Jia et al. () with application to image segmentation problems. The algorithm also avoids the regularization of TV norm and has a simpler form, which is in favor of implementing. Numerical experiments show that our algorithm works faster and more efficiently than other fast schemes, such as duality based methods and the split Bregman scheme. [ABSTRACT FROM AUTHOR]

The job-shop scheduling problems with fuzzy processing time and fuzzy due date are investigated in this paper. The ranking concept among fuzzy numbers based on possibility and necessity measures which are developed in fuzzy sets theory is introduced. And on the basis of two consistent measures in this concept, several novel objective functions are proposed. The purpose of our research is to obtain the optimal schedules based on these objective functions. A modified DE algorithm will be designed to solve these objective functions. Several jop-shop scheduling problems with fuzzy processing time and fuzzy due date are experimented to show the efficiency and comparability of our approach. Through the experimental results, the potential application of the possibility and necessity theory in the real world is shown. [ABSTRACT FROM AUTHOR]

We present a general framework of hierarchical methods for point cluster analysis on networks, and then consider individual clustering procedures and their time complexities defined by typical variants of distances between clusters. The distances considered here are the closest-pair distance, the farthest-pair distance, the average distance, the median-pair distance and the radius distance. This paper will offer a menu for users to choose hierarchical clustering algorithms on networks from a time complexity point of view. [ABSTRACT FROM AUTHOR]

very efficient technique to drastically reduce the number of multipliers and adders in narrow transition-band linear-phase finite-impulse response digital filters is to use the one-stage or multistage frequency-response masking (FRM) approach, which has been originally introduced by Lim and further improved by Lim and Lian. In these original synthesis techniques, the subfilters in the overall implementation are separately designed. As shown earlier by the authors of this contribution together with Johansson, the arithmetic complexity in one-stage FRM filter designs can be considerably reduced by using the following two-step technique for simultaneously optimizing all the subfilters. First, a suboptimal solution is found by using a simple design scheme. Second, this solution is used as a start-up solution for further optimization, which is carried out with the aid of an efficient nonlinear optimization algorithm. This paper exploits this approach to synthesizing multistage FRM filters. An example taken from the literature illustrates that both the number of multipliers and the number of adders for the resulting optimized multistage FRM filters are approximately 70 percent compared with those of the filters synthesized using the original multistage FRM filter design schemes. Additional examples are included in order to show the benefits provided by the proposed synthesis scheme over other recently published design techniques, in terms of an improved performance of the resulting solution, a higher accuracy of the solution, and a faster speed required to arrive at the best solution. [ABSTRACT FROM AUTHOR]

We devote this paper to solving the variational ineγuality of finding x* with property x* ∈ Fix(T) such that <(A-γf)x*, x-x*> ≥ 0 for all x ∈ Fix(T). Note that this hierarchical problem is associated with some convex programming problems. For solving the above VI, we suggest two algorithms: Implicit Algorithmml: xt = TPc[I - t(A - γf)]xt for all t ∈ (0, 1) and Explicit Algorithm: xn+1 = βnxn + (1 - βn)TPc[1 - αn(A - γf)]xn for all n ≥ 0. It is shown that these two algorithms converge strongly to the unique solution of the above VI. As special cases, we prove that the proposed algorithms strongly converge to the minimum norm fixed point of T. [ABSTRACT FROM AUTHOR]

This paper focuses on the facility location problem with two conflicting objectives. We observe that minimization of the total cost of a particular echelon may lead to the increase in the total cost of a supply chain as a whole. Thus, these conflicting objectives are required to be met together from a supply chain perspective. We have solved the problem formulated in mixed nonlinear programming by a multi-objective evolutionary algorithm (MOEA) known as non-dominated sorting algorithm, or NSGA II in short. Numerical example is provided to show the effect of the algorithm on the solution. [ABSTRACT FROM AUTHOR]

There are two main assumptions in multiperiodic inventory control problems. The first is the continuous review, where, depending on the inventory level, orders can happen at any time, and the other is the periodic review, where orders can only happen at the beginning of each period. In this paper, these assumptions are relaxed, and the periods between two replenishments are assumed independent and identically distributed random variables. Furthermore, the decision variables are assumed integer-type and that there are two kinds of space and budget constraints. The incremental discounts to purchase products are considered, and a combination of backorder and lost sales are taken into account for the shortages. The model of this problem is shown to be a mixed integer-nonlinear programming type, and in order to solve it, both genetic algorithm and simulated annealing approaches are employed. At the end, two numerical examples are given to demonstrate the applicability of the proposed methodologies in which genetic algorithm method performs better than simulated annealing in terms of objective function values. [ABSTRACT FROM AUTHOR]

The disassembly line is the best choice for automated disassembly of disposal products. Therefore, disassembly line should be designed and balanced so that it can work as efficiently as possible. In this paper, a mathematical model for the multi-objective disassembly line balancing problem is formalized firstly. Then, a novel multi-objective ant colony optimization (MOACO) algorithm is proposed for solving this multi-objective optimization problem. Taking into account the problem constraints, a solution construction mechanism based on the method of tasks assignment is utilized in the algorithm. Additionally, niche technology is used to embed in the updating operation to search the Pareto optimal solutions. Moreover, in order to find the Pareto optimal set, the MOACO algorithm uses the concept of Pareto dominance to dynamically filter the obtained non-dominated solution set. To validate the performance of algorithm, the proposed algorithm is measured over published results obtained from single-objective optimization approaches and compared with multi-objective ACO algorithm based on uniform design. The experimental results show that the proposed MOACO is well suited to multi-objective optimization in disassembly line balancing. [ABSTRACT FROM AUTHOR]

This paper presents a simplified algorithm for the profiling of the rack gear tool to generate the active profile associated with rolling centrodes. The algorithm is based on the enveloping surfaces principles and reduces the computational problem by proposing an approximate representation of tool’s profile using only three or four points on the profile to be generated by using Bezier representations of the surfaces. The algorithm computes the coefficients of a Bezier substitution polynomial instead of computing hundreds of points on the active profile. This simplifies the solution methodology and requires only a limited number of points along the profile to be generated. The algorithm is computationally efficient and can also be used in the case when the active profile to be generated is physically measured at a few points. Examples include mill tools, splined shafts, and gears. [ABSTRACT FROM AUTHOR]

The least-modules method allows one to process efficiently the data with anomalously great errors. The paper was devoted to the Weiszfeld algorithm enabling one to solve approximately the variational problem corresponding to the least-modules method. Estimates of nonoptimality of the algorithms’s iterations enabling one to estimate the quality of the approximate solution with anomalously great errors were obtained on the basis of the duality theory of the convex variational problems. [ABSTRACT FROM AUTHOR]

The crossed cube, which is a variation of the hypercube, possesses some properties that are superior to those of the hypercube. In this paper, we show that with the assumption of each node incident with at least two fault-free links, an n-dimensional crossed cube with up to 2 n−5 link faults can embed, with dilation one, fault-free cycles of lengths ranging from 4 to 2 n. The assumption is meaningful, for its occurrence probability is very close to 1, and the result is optimal with respect to the number of link faults tolerated. Consequently, it is very probable that algorithms executable on rings of lengths ranging from 4 to 2 n can be applied to an n-dimensional crossed cube with up to 2 n−5 link faults. [ABSTRACT FROM AUTHOR]

In this paper, we study the algorithm design aspects of three newly developed spin-wave architectures. The architectures are capable of simultaneously transmitting multiple signals using different frequencies, and allow for concurrent read/write operations. Using such features, we show a number of parallel and fault-tolerant routing schemes and introduce a set of generic parallel processing techniques that can be used for design of fast algorithms on these spin-wave architectures. We also present a set of application examples to illustrate the operation of the proposed generic parallel techniques. [ABSTRACT FROM AUTHOR]

A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. In previous works, polynomial time algorithms were found for recognizing coordinated graphs within some classes of graphs. In this paper we prove that the recognition problem for coordinated graphs is NP-hard, and it is NP-complete even when restricted to the class of {gem, C4, odd hole}-free graphs with maximum degree four, maximum clique size three and at most three cliques sharing a common vertex. [ABSTRACT FROM AUTHOR]

In this paper, we describe a successive approximation and smooth sequential quadratic programming (SQP) method for mathematical programs with nonlinear complementarity constraints (MPCC). We introduce a class of smooth programs to approximate the MPCC. Using an l1 penalty function, the line search assures global convergence, while the superlinear convergence rate is shown under the strictly complementary and second-order sufficient conditions. Moreover, we prove that the current iterated point is an exact stationary point of the mathematical programs with equilibrium constraints (MPEC) when the algorithm terminates finitely. [ABSTRACT FROM AUTHOR]

In this paper, we present a differential polynomial characteristic set algorithm for the complete symmetry classification of partial differential equations (PDEs) with some parameters. It can make the solution to the complete symmetry classification problem for PDEs become direct and systematic. As an illustrative example, the complete potential symmetry classifications of nonlinear and linear wave equations with an arbitrary function parameter are presented. This is a new application of the differential form characteristic set algorithm, i.e., Wu’s method, in differential equations. [ABSTRACT FROM AUTHOR]

In this paper, the recurrent algorithms for construction of generating ordered set of symmetric group are suggested. The bounds of transpositions’ numbers in such sets are found. [ABSTRACT FROM AUTHOR]

The paper develops the methods of harmonic disturbance compensation using the measurements of plant output variable. An approach for biased harmonic disturbance compensation is proposed. This approach is superior to known ones in some characteristics. [ABSTRACT FROM AUTHOR]

In this paper, we present an algorithm which, for a given compact orientable irreducible boundary irreducible 3-manifold M, verifies whether M contains an essential orientable surface (possibly, with boundary), whose genus is at most N. The algorithm is based on Haken’s theory of normal surfaces, and on a trick suggested by Jaco and consisting in estimating the mean length of boundary curves in an unknown essential surface of a given genus in the given manifold. [ABSTRACT FROM AUTHOR]

In this paper, we consider algorithms for constructing n-terms approximations with nonnegative coefficients. The convergence theorem is proved for a “positive” analog of the Pure Greedy Algorithm. We establish a condition on the sequence of weakness coefficients which is sufficient for the convergence of the Positive Weak Greedy Algorithm. This condition is also necessary for the class of monotone sequences. [ABSTRACT FROM AUTHOR]

In this paper, we study the convergence of Metropolis-type algorithms used in modeling statistical systems with a fluctuating number of particles located in a finite volume. We justify the use of Metropolis algorithms for a particular class of such statistical systems. We prove a theorem on the geometric ergodicity of the Markov process modeling the behavior of an ensemble with a fluctuating number of particles in a finite volume whose interaction is described by a potential bounded below and decreasing according to the law r −3−α, α ≥ 0, as r → 0. [ABSTRACT FROM AUTHOR]

This paper is devoted to bilevel optimization, a branch of mathematical programming of both practical and theoretical interest. Starting with a simple example, we proceed towards a general formulation. We then present fields of application, focus on solution approaches, and make the connection with MPECs (Mathematical Programs with Equilibrium Constraints). [ABSTRACT FROM AUTHOR]

Abstract  As new approaches and algorithms are developed for system diagnosis, it is important to reflect on existing approaches to determine their strengths and weaknesses. Of concern is identifying potential reasons for false pulls during maintenance. Within the aerospace community, one approach to system diagnosis—based on the D-matrix derived from test dependency modeling—is used widely, yet little has been done to perform any theoretical assessment of the merits of the approach. Past assessments have been limited, largely, to empirical analysis and case studies. In this paper, we provide a theoretical assessment of the representation power of the D-matrix and suggest algorithms and model types for which the D-matrix is appropriate. We also prove a surprising result relative to the difficulty of generating optimal diagnostic strategies from D-matrices. Finally, we relate the processing of the D-matrix with several diagnostic approaches and suggest how to extend the power of the D-matrix to take advantage of the power of those approaches. [ABSTRACT FROM AUTHOR]

We investigate a practical variant of the well-known graph Steiner tree problem. For a complete graph G = ( V, E ) with length function l: E → R + and two vertex subsets R ⊂ V and R ′ ⊆ R, a partial terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R ∖ R ′ belong to the leaves of this Steiner tree. The partial terminal Steiner tree problem is to find a partial terminal Steiner tree T whose total lengths ∑ (u,v ) ∈T l ( u, v ) is minimum. In this paper, we show that the problem is both NP-complete and MAX SNP-hard when the lengths of edges are restricted to either 1 or 2. We also provide an approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]

The goal of computational homogenization is to obtain the macro-scale response, normally in terms of macro-scale stress for given macro-scale deformation, via RVE-computations. In this paper we investigate, in a systematic manner, the effects of Dirichlet and Neumann boundary conditions on the RVE. Adaptive computations are carried out with respect to, in particular, control of the error in the macro-scale stress tensor. This requires the corresponding dual solutions. As a new result, it is shown how the same dual solutions can be conveniently used in computing the algorithmic tangent stiffness tensor, thereby demonstrating the “power of duality”. [ABSTRACT FROM AUTHOR]

A variables freezing method is designed for widening the possibilities of numerical application of generalized dynamic programming algorithms. Reducing the size of the memory under certain conditions, the method surmounts the “dimensional curse.” This paper is the continuation of [1–3]. [ABSTRACT FROM AUTHOR]