Dimensional Complexity and Algorithmic Efficiency

This paper uses the concept of algorithmic efficiency to present a unified theory of intelligence. Intelligence is defined informally, formally, and computationally. We introduce the concept of dimensional complexity in algorithmic efficiency and deduce that an optimally efficient algorithm has zero time complexity, zero space complexity, and an infinite dimensional complexity. This algorithm is used to generate the number line.

APPLICATION OF INTEGER CODING ACCELERATING GENETIC ALGORITHM IN RECTANGULAR CUTTING STOCK PROBLEM

An improved genetic algorithm and its application to resolve cutting stock problem arc presented. It is common to apply simple genetic algorithm （SGA） to cutting stock problem, but the huge amount of computing of SGA is a serious problem in practical application. Accelerating genetic algorithm （AGA） based on integer coding and AGA＇s detailed steps are developed to reduce the amount of computation, and a new kind of rectangular parts blank layout algorithm is designed for rectangular cutting stock problem. SGA is adopted to produce individuals within given evolution process, and the variation interval of these individuals is taken as initial domain of the next optimization process, thus shrinks searching range intensively and accelerates the evaluation process of SGA. To enhance the diversity of population and to avoid the algorithm stagnates at local optimization result, fixed number of individuals are produced randomly and replace the same number of parents in every evaluation process. According to the computational experiment, it is observed that this improved GA converges much sooner than SGA, and is able to get the balance of good result and high efficiency in the process of optimization for rectangular cutting stock problem.

TIN_DDM Buffer Surface Construction Algorithm Based on Rolling Ball Acceleration Optimization Model

In view of the TIN_DDM buffer surface existing in the construction and application of special data type,algorithm efficiency and precision are not matching;the paper applied the rolling ball model in the process of TIN_DDM buffer surface construction.Based on the precision limitation analysis of rolling ball model,the overall precision control method of rolling ball model has been established.Considering the efficiency requirement of TIN_DDM buffer surface construction,the influence principle of key sampling points and rolling ball radius to TIN_DDM buffer surface construction efficiency has been elaborated,and the rule of identifying key sampling points has also been designed.Afterwards,by erecting the numerical relationship between key sampling points and rolling ball radius,a TIN_DDM buffer surface construction algorithm based on rolling ball acceleration optimization model has been brought forward.The time complexity of the algorithm is O(n).The experiments show that the algorithm could realize the TIN_DDM buffer surface construction with high efficiency,and the algorithm precision is controlled with in 2σ.

An efficient algorithm to compute transient pressure responses of slanted wells with arbitrary inclination in reservoirs

Compared with vertical and horizontal wells, the solution and computation of transient pressure responses of slanted wells are more complex. Vertical and horizontal wells are both simplified cases of slanted wells at particular inclination, so the model for slanted wells is more general and more complex than other models for vertical and horizontal wells. Many authors have studied unsteady-state flow of fluids in slanted wells and various solutions have been proposed. However, until now, few of the published results pertain to the computational efficiency. Whether in the time domain or in the Laplace domain, the computation of integration of complex functions is necessary in obtaining pressure responses of slanted wells, while the computation of the integration is complex and time-consuming. To obtain a perfect type curve the computation time is unacceptable even with an aid of high-speed computers. The purpose of this paper is to present an efficient algorithm to compute transient pressure distributions caused by slanted wells in reservoirs. Based on rigorous derivation, the transient pressure solution for slanted wells of any inclination angle is presented. Assuming an infinite-conductivity wellbore, the location of the equivalent-pressure point is determined. More importantly, according to the characteristics of the integrand in a transient pressure solution for slanted wells, the whole integral interval is partitioned into several small integral intervals, and then the method of variable substitution and the variable step-size piecewise numerical integration are employed. The amount of computation is significantly reduced and the computational efficiency is greatly improved. The algorithm proposed in this paper thoroughly solved the difficulty in the efficient and high-speed computation of transient pressure distribution of slanted wells with any inclination angle.

Enhanced Reliability in Network Function Virtualization by Hybrid Hexagon-Cost Efficient Algorithm

In this,communication world, the Network Function Virtualization concept is utilized for many businesses, small services to virtualize the network nodefunction and to build a block that may connect the chain, communication services.Mainly, Virtualized Network Function Forwarding Graph (VNF-FG) has beenused to define the connection between the VNF and to give the best end-to-endservices. In the existing method, VNF mapping and backup VNF were proposedbut there was no profit and reliability improvement of the backup and mapping ofthe primary VNF. As a consequence, this paper offers a Hybrid Hexagon-CostEfficient algorithm for determining the best VNF among multiple VNF and backing up the best VNF, lowering backup costs while increasing dependability. TheVNF is chosen based on the highest cost-aware important measure (CIM) rate,which is used to assess the relevance of the VNF forwarding graph.To achieveoptimal cost-efficiency, VNF with the maximum CIM is selected. After the selection process, updating is processed by three steps which include one backup VNFfrom one SFC, two backup VNF from one Service Function Chain (SFC),and twobackup VNF from different SFC. Finally, this proposed method is compared withCERA, MinCost, MaxRbyInr based on backup cost, number of used PN nodes,SFC request utility, and latency. The simulation result shows that the proposedmethod cuts down the backup cost and computation time by 57% and 45% compared with the CER scheme and improves the cost-efficiency. As a result, this proposed system achieves less backup cost, high reliability, and low timeconsumption which can improve the Virtualized Network Function operation.

AN EFFICIENT FINITE-DIFFERENCE ALGORITHM FOR COMPUTING AXISYMMETRIC TRANSONIC NACELLE FLOW FIELDS

A finite difference method for computing the axisymmetric, transonic flows over a nacelle is presented in this paper. By use of the conservative full-potential equation, body-fitted grid, and the exact boundary conditions, a new AF scheme is constructed according to the criterion of optimum convergence. The proposed scheme has been applied to transonic nacelle flow problems. Computation for several nacelles shows the rapid convergence of this scheme and excellent agreement with the experimental results.

Framed-Quadtree Path Planning for an Underwater Vehicle with the Task of Tracking a Moving Target

An autonomous underwater vehicle (AUV) must use an algorithm to plan its path to distant, mobile offshore objects. Because of the uneven distribution of obstacles in the real world, the efficiency of the algorithm decreases if the global environment is represented by regular grids with all of them at the highest resolution. The framed quadtree data structure is able to more efficiently represent the environment. When planning the path, the dynamic object is expressed instead as several static objects which are used by the path planner to update the path. By taking account of the characteristics of the framed quadtree, objects can be projected on the frame nodes to increase the precision of the path. Analysis and simulations showed the proposed planner could increase efficiency while improving the ability of the AUV to follow an object.

Distributed Clustering Algorithm for Energy Efficiency and Load-Balance in Large-Scale Multi-Agent Systems

To improve the energy efficiency and load-balance in large-scale multi-agent systems, a large-scale distributed cluster algorithm is proposed. At first, a parameter describing the spatial distribution of agents is designed to assess the information spreading capability of an agent. Besides, a competition resolution mechanism is proposed to tackle the competition problem in large-scale multiagent systems. Thus, the proposed algorithm can balance the load, adjust the system network locally and dynamically, reduce system energy consumption. Finally, simulations are presented to demonstrate the superiority of the proposed algorithm.

Repairable Configuration Optimization Model under Two-Echelon Inventory

Spares inventory configuration optimization is an effective way to improve readiness and reduce life cycle cost of equipment.Through analyzing two-echelon spares support system,the METRIC model basic theory was used.An inventory configuration optimization model of two-echelon spares support system was proposed which took the spares expected shortfall as the object and made the minimum repairable parts expected shortfall instead of the maximum spares supportability as the objective function.Marginal efficiency analysis algorithm was applied to optimizing the spares configuration and generating a rational spares inventory configuration.Finally,several examples are given to verify the model.

Efficient model building in active appearance model for rotated face

This paper proposes the efficient model building in active appearance model(AAM) for the rotated face.Finding an exact region of the face is generally difficult due to different shapes and viewpoints.Unlike many papers about the fitting method of AAM,this paper treats how images are chosen for fitting of the rotated face in modelling process.To solve this problem,databases of facial rotation and expression are selected and models are built using Procrustes method and principal component analysis(PCA).These models are applied in fitting methods like basic AAM fitting,inverse compositional alignment(ICA),project-out ICA,normalization ICA,robust normalization inverse compositional algorithm(RNIC)and efficient robust normalization algorithm(ERN).RNIC and ERN can fit the rotated face in images efficiently.The efficiency of model building is checked using sequence images made by ourselves.

Distributed Algorithms for Event Reporting in Mobile-Sink WSNs for Internet of Things

Wireless Sensor Networks（WSNs） have many applications, such as climate monitoring systems, fire detection, smart homes, and smart cities. It is expected that WSNs will be integrated into the Internet of Things（IoT）and participate in various tasks. WSNs play an important role monitoring and reporting environment information and collecting surrounding context. In this paper we consider a WSN deployed for an application such as environment monitoring, and a mobile sink which acts as the gateway between the Internet and the WSN. Data gathering is a challenging problem in WSNs and in the IoT because the information has to be available quickly and effectively without delays and redundancies. In this paper we propose several distributed algorithms for composite event detection and reporting to a mobile sink. Once data is collected by the sink, it can be shared using the IoT infrastructure. We analyze the performance of our algorithms using WSNet simulator, which is specially designed for event-based WSNs. We measure various metrics such as average residual energy, percentage of composite events processed successfully at the sink, and the average number of hops to reach the sink.

Efficient Haplotype Inference Algorithms in One Whole Genome Scan for Pedigree Data with Non-genotyped Founders

An efficient rule-based algorithm is presented for haplotype inference from general pedigree genotype data, with the assumption of no recombination. This algorithm generalizes previous algorithms to handle the cases where some pedigree founders are not genotyped, provided that for each nuclear family at least one parent is genotyped and each non-genotyped founder appears in exactly one nuclear family. The importance of this generalization lies in that such cases frequently happen in real data, because some founders may have passed away and their genotype data can no longer be collected. The algorithm runs in O（m^3n^3） time, where m is the number of single nucleotide polymorphism （SNP） loci under consideration and n is the number of genotyped members in the pedigree. This zero-recombination haplotyping algorithm is extended to a maximum parsimoniously haplotyping algorithm in one whole genome scan to minimize the total number of breakpoint sites, or equivalently, the number of maximal zero-recombination chromosomal regions. We show that such a whole genome scan haplotyping algorithm can be implemented in O（m^3n^3） time in a novel incremental fashion, here m denotes the total number of SNP loci along the chromosome.

An integrated stochastic model and algorithm for multi-product newsvendor problems

In this paper,a multi-product newsvendor problem is formulated as a random nonlinear integrated optimization model by taking into consideration the selling price,the producing and outsourcing quantities,and the nonlinear budget constraint.Different from the existing models,the demands of products depend on the prices,as well as being timevarying due to random market fluctuation.In addition,outsourcing strategy is adopted to deal with possible shortage caused by the limited capacity.Consequently,the constructed model is involved with joint optimization of the producing and outsourcing quantities,and the selling prices of all the products.For this model with continuous random demands,we first transform it into a nonlinear programming problem by expectation method.Then,an efficient algorithm,called the feasible-direction-based spectral conjugate gradient algorithm,is developed to find a robust solution of the model.By case study and sensitivity analysis,some interesting conclusions are drawn as follows:(a)Budget is a critical constraint for optimizing the decision-making of the retailer,and there exist different threshold values of the budget for the substitute and complementarity scenarios.(b)The price sensitivity matrix seriously affects the maximal expected profit mainly through affecting the optimal outsourcing quantity.

An Efficient Algorithm for Processing Multi-Relation Queries in Relational Databases

After a relation scheme R is decomposed into the set of schemes ρ={R_1,...,R_n},we may pose queries as if R existed in the database,taking a join of R_i's,when it is necessary to implement the query.Suppose a query involves a set of attributes S(?)R,we want to find the smallest subset of ρ whose union includes S.We prove that the problem is NP-complete and present a polynomial-bounded approximation algorithm.A subset of ρ whose union includes S and has a decomposition into 3NF with a lossless join and preservation of dependencies is given in the paper.

Acceleration Strategies Based on an Improved Bubble Packing Method

The bubble packing method can generate high-quality node sets in simple and complex domains.However,its efficiency remains to be improved.This study is a part of an ongoing effort to introduce several acceleration schemes to reduce the cost of simulation.Firstly,allow the viscosity coefficient c in the bubble governing equations to change according the coordinate of the bubble which are defined separately as odd and normal bubbles,and meanwhile with the saw-shape relationship with time or iterations.Then,in order to relieve the over crowded initial bubble placement,two coefficients w1 and w2 are introduced to modify the insertion criterion.The range of those two coefficients are discussed to be w1=1,w2∈[0.5,0.8].Finally,a self-adaptive termination condition is logically set when the stable system equilibrium is achieved.Numerical examples illustrate that the computing cost can significantly decrease by roughly 80%via adopting various combination of proper schemes(except the uniform placement example),and the average qualities of corresponding Delaunay triangulation substantially exceed 0.9.It shows that those strategies are efficient and can generate a node set with high quality.

I/O Efficient Early Bursting Cohesive Subgraph Discovery in Massive Temporal Networks

Temporal networks are an effective way to encode temporal information into graph data losslessly.Finding the bursting cohesive subgraph(BCS),which accumulates its cohesiveness at the fastest rate,is an important problem in temporal networks.The BCS has a large number of applications,such as representing emergency events in social media,traffic congestion in road networks and epidemic outbreak in communities.Nevertheless,existing methods demand the BCS lasting for a time interval,which neglects the timeliness of the BCS.In this paper,we design an early bursting cohesive subgraph(EBCS)model based on the k-core to enable identifying the burstiness as soon as possible.To find the EBCS,we first construct a time weight graph(TWG)to measure the bursting level by integrating the topological and temporal information.Then,we propose a global search algorithm,called GS-EBCS,which can find the exact EBCS by iteratively removing nodes from the TWG.Further,we propose a local search algorithm,named LS-EBCS,to find the EBCS by first expanding from a seed node until obtaining a candidate k-core and then refining the k-core to the result subgraph in an optimal time complexity.Subsequently,considering the situation that the massive temporal networks cannot be completely put into the memory,we first design an I/O method to build the TWG and then develop I/O efficient global search and local search algorithms,namely I/O-GS and I/O-LS respectively,to find the EBCS under the semi-external model.Extensive experiments,conducted on four real temporal networks,demonstrate the efficiency and effectiveness of our proposed algorithms.For example,on the DBLP dataset,I/O-LS and LS-EBCS have comparable running time,while the maximum memory usage of I/O-LS is only 6.5 MB,which is much smaller than that of LS-EBCS taking 308.7 MB.

ON BLOCK MATRICES ASSOCIATED WITH DISCRETE TRIGONOMETRIC TRANSFORMS AND THEIR USE IN THE THEORY OF WAVE PROPAGATION

Block matrices associated with discrete Trigonometric transforms （DTT＇s） arise in the mathematical modelling of several applications of wave propagation theory including discretizations of scatterers and radiators with the Method of Moments, the Boundary Element Method, and the Method of Auxiliary Sources. The DTT＇s are represented by the Fourier, Hartley, Cosine, and Sine matrices, which are unitary and offer simultaneous diagonalizations of specific matrix algebras. The main tool for the investigation of the aforementioned wave applications is the efficient inversion of such types of block matrices. To this direction, in this paper we develop an efficient algorithm for the inversion of matrices with U-diagonalizable blocks （U a fixed unitary matrix） by utilizing the U- diagonalization of each block and subsequently a similarity transformation procedure. We determine the developed method＇s computational complexity and point out its high efficiency compared to standard inversion techniques. An implementation of the algorithm in Matlab is given. Several numerical results are presented demonstrating the CPU-time efficiency and accuracy for ill-conditioned matrices of the method. The investigated matrices stem from real-world wave propagation applications.