Search

The paper considers algorithms for solving inverse scattering problems based on the discretization of the Gelfand–Levitan–Marchenko integral equations, associated with the system of nonlinear Schrödinger equations of the Manakov model. The numerical algorithm of the first order approximation for solving the scattering problem is reduced to the inversion of a series of nested block Toeplitz matrices using the Levinson-type bordering method. Increasing the approximation accuracy violates the Toeplitz structure of block matrices. Two algorithms are described that solve this problem for second order accuracy. One algorithm uses a block version of the Levinson bordering algorithm, which recovers the Toeplitz structure of the matrix by moving some terms of the systems of equations to the right-hand side. Another algorithm is based on the Toeplitz decomposition of an almost block-Toeplitz matrix and the Tyrtyshnikov bordering algorithm. The speed and accuracy of calculations using the presented algorithms are compared on an exact solution (the Manakov vector soliton). [ABSTRACT FROM AUTHOR]

A good stacking method can increase the packaging utility rate and reduce production costs. Much research has focused on 2D arrangements for rectangular, circular, or irregular shapes and regularly shaped 3D objects such as rectangular boxes. Genetic algorithms, simulated annealing, and other heuristic algorithms have been proposed. Recent research on the stacking of irregular-shaped 3D stone pieces has focused on balancing one stone piece on top of others to form one or more vertical towers, given the geometry of the stone pieces and the number of stone pieces available for the task. Stacking irregular-shaped 3D objects in a package is common in industry. However, there has been relatively little emphasis on the development of algorithms for stacking irregular-shaped 3D objects in a fixed-size container without prior knowledge of the stone geometries and the number of pieces available, with the goal of packing as many stone pieces as possible while maintaining stability. In this paper, three heuristic algorithms are proposed to solve the problem of nesting irregularly shaped stone pieces in layers within a container. All three algorithms use the following approach: (1) approximate the alignment of irregular shapes to a cluster of straight lines; (2) arrange stones one by one at the approximated angles using a step-by-step process; (3) for stability, consider the weight of the stone pieces based on pixel calculations. An automated real-time stacking system—including sensors, pneumatic suction cups, webcams, conveyor, robot, and programmable logic controller—was developed to evaluate the proposed algorithms using space utilization, stability, and cycle time as measures of performance. The developed algorithms and an existing stacking algorithm (bottom left most, or BLM) were tested using 25 sequences of 30 randomly ordered stone pieces. Results suggest that the developed algorithms effectively solve the stone piece packing problem. All three were significantly better than the BLM algorithm in terms of space utilization and stability, and there was no difference in cycle time. Algorithm 3 was better than Algorithms 1 and 2. [ABSTRACT FROM AUTHOR]

Some efficient top-k algorithms, i.e., Fagin's Algorithm, threshold algorithm (TA), and best position algorithm (BPA), can be used to answer k nearest neighbor (kNN) queries. However, extending the existing algorithms without further changes to the algorithms themselves would not be efficient since there are the different characteristics between the kNN queries and top-k queries. For example, the kNN queries are more distance-sensitive rather than the position of data points. Second, it is necessary to add some novel parallel heuristics and pruning policies for the kNN queries. Third, there are still many redundant random accesses among FA, TA, and BPA. In this paper, we address aforementioned these problems and take these algorithms to answer parallel kNN (PkNN) queries in spatial databases. We integrate the advantages of the B + -tree and Open MP programming and propose three efficient parallel kNN query algorithms, namely distance priority-based PkNN, optimized PkNN, and partition-based PkNN. Our performance evaluation shows that our proposed algorithms achieve significant improvement in comparison with existing algorithms, i.e., BPA and BPA2. In addition, our approaches are also capable of returning kNN results incrementally which greatly shorten the query response time and enhance user experience. [ABSTRACT FROM AUTHOR]

We propose a dead-end control algorithm for the exact solution of NP-hard combinatorial optimization problems. The efficiency of the algorithm is demonstrated by examples of solving the set-partition and 0-1 knapsack problems. The paper also shows that the use of the idea of dead-end controls when implementing the dynamic programming method can considerably reduce the number of problem state variables at each optimization step. A comparative analysis of the proposed method with known algorithms for solving these problems is carried out. [ABSTRACT FROM AUTHOR]

The decision making of a suitable heating, ventilating and air conditioning system's set-point temperature is an energy and environmental challenge in our society. In the present paper, a general framework to define such temperature based on a dynamic adaptive comfort algorithm is proposed. Due to the fact that the thermal comfort of the occupants of a building has different ranges of acceptability, this method is applied to learn such comfort temperature with respect to the running mean temperature and therefore to decide the suitable range of indoor temperature. It is demonstrated that this solution allows to dynamically build an adaptive comfort algorithm, an algorithm based on the human being's thermal adaptability, without applying the traditional theory. The proposed methodology based on the K-Nearest-Neighbour algorithm was tested and compared with data from an experimental thermal comfort field study carried out in a mixed mode building in the south-western area of Spain and with the Support Vector Machine method. The results show that K-Nearest-Neighbour algorithm represents the pattern of thermal comfort data better than the traditional solution and that it is a suitable method to learn the thermal comfort area of a building and to define the set-point temperature for a heating, ventilating and air-conditioning system. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of constructing a correction algorithm with the aim of increasing the adaptive properties of the ΣΠ-neuron, relying solely on the structure of the ΣΠ-neuron itself. To build the corrector, the logical-algebraic method of data analysis is used. Comparison of the advantages of the neural network approach and the logical-algebraic method suggests that a combined approach to the organization of the neural network improves its efficiency and allows one to build a set of rules that reveal hidden patterns in a given subject area, thus improving the quality of the recognition system. [ABSTRACT FROM AUTHOR]

Purpose: Fractures of the femoral shaft in children are common. The rates of bone growth and remodeling in children vary according to their ages, which affect their respective management. Methods: This paper evaluates the incidence and patterns of pediatric femoral shaft fracture and the current concepts of treatments available. Results: The type of fracture—closed or open; stable or unstable—needs to be taken into account. Child abuse should be suspected in fractures sustained by infants. For younger children, non-surgical management is preferred, which include Pavlik harness (< 6 months old) and early spica casting (6 months to 6 years old). Older children (> 6 years old) usually benefit from surgical treatments as outcomes of non-surgical alternatives are worse and are associated with prolonged recovery times. These operative measures for older children that are 6–12 years old include elastic stable intramedullary nailing and submuscular plating. Factors to be considered when devising an appropriate intervention include body mass, location of injury, and nature of fracture. For adolescent and skeletally mature teenagers (> 12 years old), rigid antegrade entry intramedullary fixation is indicated. In the event of open fractures or polytrauma, external fixation should be considered as a temporary treatment method for initial fracture stabilization. Conclusion: An age-based and evidence-based algorithm has been proposed to guide surgeons in the process of evaluating an appropriate treatment. [ABSTRACT FROM AUTHOR]

Node similarity search on graphs has wide applications in recommendation, link prediction, to name just a few. However, existing studies are insufficient due to two reasons: (i) the scale of the real-world graph is growing rapidly, and (ii) vertices are always associated with complex attributes. In this paper, we propose an efficiently distributed framework to support node similarity search on massive graphs, which considers both graph structure correlation and node attribute similarity in metric spaces. The framework consists of preprocessing stage and query stage. In the preprocessing stage, a parallel KD-tree construction (KDC) algorithm is developed to form a newly defined graph so-called hybrid graph, in order to integrate node attribute similarity into the original graph. To equally divide graph vertices into subsets, KDC adopts the KD-tree partitioning after the pivot mapping. In addition, two metric pruning rules and an optimized allocation strategy are presented to reduce communication and computation costs. In the query stage, based on the formed hybrid graph, we develop similarity search methods using random walk with restart (RWR) to measure node similarity. To boost efficiency, we derive tight bounds to rapidly shrink the search region. Extensive experiments with three real massive graphs are conducted to verify the effectiveness, efficiency, and scalability of our proposed techniques. [ABSTRACT FROM AUTHOR]

Classification accuracy provided by a machine learning model depends a lot on the feature set used in the learning process. Feature selection (FS) is an important and challenging preprocessing technique which helps to identify only the relevant features from a dataset, thereby reducing the feature dimension as well as improving the classification accuracy at the same time. The binary version of whale optimization algorithm (WOA) is a popular FS technique which is inspired from the foraging behavior of humpback whales. In this paper, an embedded version of WOA called embedded chaotic whale survival algorithm (ECWSA) has been proposed which uses its wrapper process to achieve high classification accuracy and a filter approach to further refine the selected subset with low computation cost. Chaos has been introduced in the ECWSA to guide selection of the type of movement followed by the whales while searching for prey. A fitness-dependent death mechanism has also been introduced in the system of whales which is inspired from the real-life scenario in which whales die if they are unable to catch their prey. The proposed method has been evaluated on 18 well-known UCI datasets and compared with its predecessors as well as some other popular FS methods. The source code of ECWSA can be found in https://github.com/Ritam-Guha/ECWSA. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of finding the generators of the solution space for a system of inequalities A ⊗ x ≥ x in max-plus algebra. It provides an improved algorithm which can be used to find a smaller set of generators for the solution space by skipping a large number of invalid generators. [ABSTRACT FROM AUTHOR]

This paper presents two algorithms. The first decides the existence of a pointed homotopy between given simplicial maps f , g : X → Y , and the second computes the group [ Σ X , Y ] ∗ of pointed homotopy classes of maps from a suspension; in both cases, the target Y is assumed simply connected. More generally, these algorithms work relative to A ⊆ X . [ABSTRACT FROM AUTHOR]

In recent years, the backward trajectory model has been widely used in the research of meteorological and atmospheric environmental quality. This paper presents a comprehensive study on a stepwise clustering analysis algorithm in the clustering process of backward trajectory model and an application of the clustering analysis of single-particle backward trajectory in 2016 in Changchun City. This study starts with an analysis of the original stepwise clustering algorithm and its application to a clustering process of 8784 backward trajectories during 48 h in Changchun City as a benchmark test case. Then, two improvements are made in the algorithm: First, in the process of finding the optimal classification, the algorithm complexity is improved from original O(n3) to O(log(n)*n2) through algorithm improvement. The algorithm performance is enhanced by log(n) times. Second, in the process of re-establishing the classification, the algorithm complexity is improved from the original O(m*n2) to O(m*log(n)*n), that is another algorithm performance improvement by a factor of log(n). Therefore, the accumulative execution efficiency improvement through the algorithm optimization is 2*log(n) times, which has been further verified in the practical application in Changchun City. [ABSTRACT FROM AUTHOR]

In this paper, we propose and analyse a new unbiased stochastic approach for solving a class of integral equations. We study and compare the proposed unbiased approach against the known biased Monte Carlo method based on evaluation of truncated Liouville-Neumann series. We also compare the proposed algorithm against the deterministic Nystrom method. Extensions of the unbiased method for the weak and global solutions are described. Extensive numerical experiments have been performed to support the theoretical studies regarding the convergence of the unbiased algorithms. The results are compared to the best known biased Monte Carlo algorithms for numerical integration done in our previous studies. Conclusions about the applicability and efficiency of the proposed algorithms have been drawn. [ABSTRACT FROM AUTHOR]

This paper substantiates the urgency of developing theoretical foundations, methods, and algorithms for cryptographic protection of color image pixels using problem-oriented multifunctional data structuring and representing codes of color image pixels in the Rademacher, Chrestenson, Rademacher–Chrestenson, Haar–Chrestenson, and Galois systems and investigates the possibility of increasing the operating speed of algorithms for transforming, processing, and recognizing digital images using the modular arithmetic of residue number systems based on the mathematics of arithmetic operations of a non-positional residue number system. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithm estimating structural equation models by using the generalized structured component analysis (GSCA) formulation. In GSCA models, the latent variables are composites. The weights are estimated in conjunction with the other model parameters, optimizing a genuine least squares criterion. The new algorithm is designed for three subclasses often used in applications. Linear regressions are alternated for different sets of parameters according to the nonlinear manner in which the parameters are incorporated in the model. The new algorithm is compared with two existing ones by using different examples from the literature, as well as simulations. On the average the proposed algorithm produces better criterion values compared to the other two ones. [ABSTRACT FROM AUTHOR]

Purpose: Antipsychotics (APs) are commonly used to manage neuropsychiatric symptoms (NPS) in elderly patients with dementia, even though several large studies have demonstrated an association between AP treatment and increased morbidity and mortality in people with dementia. The aim of this study is to review the scientific literature of the use of AP in the elderly with dementia and to propose an algorithm to assist in decision-making regarding the withdrawal of APs. Methods: A computerized literature search (MEDLINE: 1966 to December 2016, EMBASE: 1982 to December 2016) was used to locate relevant literature. Keywords in the search included terms from Medical Subject Headings (MESH) and EMBASE thesaurus (EMTREE). The following terms were used in the MESH database and EMTREE thesaurus: Aged, Antipsychotic Agents, Behavioral Symptoms and Dementia. Results: Earlier studies of APs used in elderly patients with dementia suggest that, in most elderly demented patients, APs can be withdrawn with no effect on behaviour. These patients are likely to benefit from the algorithm we propose to assist clinicians in the withdrawal of APs. Conclusions: In this paper, we review the potential risks and benefits of discontinuing AP treatment in elderly demented patients with NPS and propose an algorithm to assist in decision-making regarding AP withdrawal. [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]

Cluster analysis as an important function of the data mining has made great progress in recent years a series of methods for analysis of accuracy provides a solid foundation. This paper proposes the novel pattern clustering algorithm based on particle swarm optimization joint adaptive wavelet neural network model. Nonlinear adaptive filter has the stronger ability of that signal processing. However, due to complicated calculation of the nonlinear adaptive filter, the actual use of linear adaptive filter is still. To deal with this challenge, we integrate the wavelet neural network for modification. Usually, the wavelet neural network learning process using the gradient descent method, even if the error function that along the negative gradient direction, and which requires the step length direction along the negative gradient direction. As well, we revise the PSO to enhance the wavelet NN in the process of search, the equilibrium relation between the global search ability and local search ability for the success of the algorithm plays an important role. With this modification, our method obtains the better performance. The experimental result shows the feasibility and the effectiveness of the method compared with the other latest and state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Springback is the most common defect in sheet metal forming, especially for the advanced high-strength steel (AHSS) parts. The compensation method is an effective way to overcome this defect by modifying the die-face. A new geometrical springback compensation algorithm based on the advanced displacement adjustment (DA) method is proposed in this paper for automobile AHSS parts. The die-face is reconstructed by the non-uniform rational B-spline surface with the advantage of UV curves; furthermore, the continuity and topology of the die-face are also studied. The high-quality geometry compensation die-face obtained from this algorithm can be directly applied to actual machining. To reduce the time and cost of the die manufacturing, this algorithm is seamlessly integrated into the CATIA platform. A new compensation user-defined feature is created, which can meet the need for iterative compensation and parametric association. At the end of this paper, two engineering examples of AHSS parts verify the feasibility and validity of this algorithm and system. [ABSTRACT FROM AUTHOR]

The concept of rainbow connection was introduced by Chartrand et al. [] in 2008. It is interesting and recently quite a lot papers have been published about it. In this survey we attempt to bring together most of the results and papers that dealt with it. We begin with an introduction, and then try to organize the work into five categories, including (strong) rainbow connection number, rainbow k-connectivity, k-rainbow index, rainbow vertex-connection number, algorithms and computational complexity. This survey also contains some conjectures, open problems and questions. [ABSTRACT FROM AUTHOR]

In the paper, we introduce a class of delay differential variational inequalities consisting of a system of delay differential equations and variational inequalities. The existence conclusion of Carathéodory's weak solution for delay differential variational equalities is obtained. Furthermore, an algorithm for solving the delay differential variational inequality is shown, and the convergence analysis for the algorithm is given. Finally, a numerical example is given to verify the validity of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new method to analyze the convergence of the standard finite element method for the noncoercive impulse control quasi-variational inequality (QVI). L convergence of the approximation is derived as a result of the geometrical convergence of a Bensoussan-Lions algorithm type and uniform error estimate between the continuous algorithm and its finite element counterpart. This approach is completely different from the one inroduced in [2] as it enables us to derive the error estimate through a computational iterative scheme. [ABSTRACT FROM AUTHOR]

As an increase in gastroesophageal reflux disease (GERD) has been reported in Japan, and public interest in GERD has been increasing, the Japanese Society of Gastroenterology published the Evidence-based Clinical Practice Guidelines for GERD (1st edition) in 2009. Six years have passed since its publication, and there have been a large number of reports in Japan concerning the epidemiology, pathophysiology, treatment, and Barrett's esophagus during this period. By incorporating the contents of these reports, the guidelines were completely revised, and a new edition was published in October 2015. The revised edition consists of eight items: epidemiology, pathophysiology, diagnosis, internal treatment, surgical treatment, esophagitis after surgery of the upper gastrointestinal tract, extraesophageal symptoms, and Barrett's esophagus. This paper summarizes these guidelines, particularly the parts related to the treatment for GERD. In the present revision, aggressive proton pump inhibitor (PPI) maintenance therapy is recommended for severe erosive GERD, and on-demand therapy or continuous maintenance therapy is recommended for mild erosive GERD or PPI-responsive non-erosive GERD. Moreover, PPI-resistant GERD (insufficient symptomatic improvement and/or esophageal mucosal break persisting despite the administration of PPI at a standard dose for 8 weeks) is defined, and a standard-dose PPI twice a day, change in PPI, change in the PPI timing of dosing, addition of a prokinetic drug, addition of rikkunshito (traditional Japanese herbal medicine), and addition of histamine H2-receptor antagonist are recommended for its treatment. If no improvement is observed even after these treatments, pathophysiological evaluation with esophageal impedance-pH monitoring or esophageal manometry at an expert facility for diseases of the esophagus is recommended. [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]

Recently, applications of cooperative game theory to economic allocation problems have gained popularity. In many such allocation problems there is some hierarchical ordering of the players. In this paper we consider a class of games with a permission structure describing situations in which players in a cooperative TU-game are hierarchically ordered in the sense that there are players that need permission from other players before they are allowed to cooperate. The corresponding restricted game takes account of the limited cooperation possibilities by assigning to every coalition the worth of its largest feasible subset. In this paper we provide a polynomial time algorithm for computing the nucleolus of the restricted games corresponding to a class of games with a permission structure which economic applications include auction games, dual airport games, dual polluted river games and information market games. [ABSTRACT FROM AUTHOR]

Recently, a multiple-material stereolithography (MMSL) system was introduced, which included the novel feature of stacking different photocurable resins to produce a multiple-material part. This process is capable of fabricating intricately detailed parts with smooth surface finish and internal structures of various colors. However, the MMSL system requires a washing process when switching materials, and this additional step increases the fabrication time and also introduces deformations in the build structure as registration errors accumulate. Consequently, reducing the number of material changeovers in this process is a priority, and the minimum number of changeovers is imposed in part by the sweep interference between layers of different materials. Fortunately, the use of low-viscosity resins permits possible fabrication without sweeping. As a result, multiple layers of one material can be continuously built without changing resins, and subsequently, a different low-viscosity material can be added without resulting in sweep obstruction with the original layers. In this paper, a stacking simulation, which determines the maximum number of layers possible to be continuously built between material changeovers, is described. This paper presents a novel interference-detection algorithm, which identifies interference by inspecting the overlap between loop segments. In addition, the algorithm successfully manages the triangulation errors that occur at a curved surface when two materials are adjacent within a layer. Finally, several practical examples are shown to verify the algorithm and provide compelling evidence that the proposed algorithm is effective and applicable in MMSL. [ABSTRACT FROM AUTHOR]

The lack of effective and efficient schedule-based pathfinding algorithms for transit networks has limited the application of GIS in transit trip planning services. This paper introduces a schedule-based path finding algorithm for transit networks. Based on a pattern-centered spatiotemporal transit network model, the algorithm searches the network by following route patterns. A pattern is a spatial layout of a route in transit terminology. A route usually has many patterns to serve various locations at different times. This path search algorithm is significantly different from traditional shortest path algorithms that are based on adjacent node search. By establishing a set of lemmas and theorems the paper proves that paths generated by the PFS algorithm are schedule-coordinated fastest paths for trips with given constraints. After analyzing computation and database query complexities of the algorithm the paper indicates that the PFS is efficient in computation and database query. Finally, effectiveness and efficiency of the algorithm are demonstrated by implementations in GIS-based online transit trip planners in Wisconsin, US. [ABSTRACT FROM AUTHOR]

The hypercube, or n-cube, has been widely used as the interconnection network in parallel computers. However, the major drawback of the hypercube is the increase in the number of communication links for each node with the increase in the total number of nodes in the system. This paper introduces a new interconnection network, namely dual-cube, for large-scale parallel computers and describes the algorithms for efficient collective communications in dual-cube. The dual-cube network mitigates the problem of increasing number of links in the large-scale hypercube network while retains hypercube’s topological properties. Design of efficient routing algorithms for collective communications is the key issue for any interconnection network. In this paper, we show that the collective communications can be done in dual-cube with almost the same communication times as in hypercube. [ABSTRACT FROM AUTHOR]

Persistent homology with coefficients in a field $$\mathbb {F}$$ coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substantially the amount of matrix operations. In addition, we propose a heuristic to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology. [ABSTRACT FROM AUTHOR]

In the arsenal of resources for computer memory system performance improvement, predictors have gained an increasing role in the past years. They can suppress latencies when accessing cache or main memory. In our previous work we considered using predictors to decrease Synchronized Dynamic Random Access Memory (SDRAM) latency. If one wants to apply several predictors at the same time, there has to exist proper synchronization of the predictors. This stems from the fact that SDRAM controller has to activate and update each of the predictors at proper times, while at the same time executing standard SDRAM commands, such as opening/closing rows, accessing columns, etc. In this paper we propose a universal synchronization algorithm for predictors for SDRAM memories, which can be used with practically any predictor, regardless of its specific method of predicting, and with very little or no modifications. [ABSTRACT FROM AUTHOR]

We introduce algorithms for the computation of homology, cohomology, and related operations on cubical cell complexes, using the technique based on a chain contraction from the original chain complex to a reduced one that represents its homology. This work is based on previous results for simplicial complexes, and uses Serre's diagonalization for cubical cells. An implementation in C++ of the introduced algorithms is available at together with some examples. The paper is self-contained as much as possible, and is written at a very elementary level, so that basic knowledge of algebraic topology should be sufficient to follow it. [ABSTRACT FROM AUTHOR]

Advanced forging simulation codes leads die designer toward more efficient methods in waste material reduction. In this paper, an approach has been presented to reduce waste material by controlling material flow with variable gutter. Initially, an algorithm is offered for decision making. A control criterion (δ) has been suggested in order to determine the new modified gutter thickness and width. A new formula has been offered to calculate the new dimensions of gutter width and thickness base on (δ) criterion in each step. To evaluate the effectiveness of the proposed criterion and formula a set of Finite volume and finite element simulations has been done on different forging parts. Then a 'T shape' part has been chosen as a case study to investigate the effect of variable gutter width method and variable gutter thickness method separately. The FVM and FEM simulation results for variable thickness and width show a waste material reduction of 12% and 14%, respectively. Finally an experimental test has been setup to verify the simulation result of variable gutter thickness method. The simulation and experimental results have a good agreement. [ABSTRACT FROM AUTHOR]

The k-distance domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or within distance k from some vertex of D, where k is a positive integer. In the present paper, by using labeling method, a linear-time algorithm for k-distance domination problem on block graphs is designed. [ABSTRACT FROM AUTHOR]

Bat algorithm (BA) is a new stochastic optimization technique for global optimization. In the paper, we introduce both simulated annealing and Gaussian perturbations into the standard bat algorithm so as to enhance its search performance. As a result, we propose a simulated annealing Gaussian bat algorithm (SAGBA) for global optimization. Our proposed algorithm not only inherits the simplicity and efficiency of the standard BA with a capability of searching for global optimality, but also speeds up the global convergence rate. We have used BA, simulated annealing particle swarm optimization and SAGBA to carry out numerical experiments for 20 test benchmarks. Our simulation results show that the proposed SAGBA can indeed improve the global convergence. In addition, SAGBA is superior to the other two algorithms in terms of convergence and accuracy. [ABSTRACT FROM AUTHOR]

This work focuses on the most commonly used binarization method: Sauvola's. It performs relatively well on classical documents, however, three main defects remain: the window parameter of Sauvola's formula does not fit automatically to the contents, it is not robust to low contrasts, and it is not invariant with respect to contrast inversion. Thus, on documents such as magazines, the contents may not be retrieved correctly, which is crucial for indexing purpose. In this paper, we describe how to implement an efficient multiscale implementation of Sauvola's algorithm in order to guarantee good binarization for both small and large objects inside a single document without adjusting manually the window size to the contents. We also describe how to implement it in an efficient way, step by step. This algorithm remains notably fast compared to the original one. For fixed parameters, text recognition rates and binarization quality are equal or better than other methods on text with low and medium x-height and are significantly improved on text with large x-height. Pixel-based accuracy and OCR evaluations are performed on more than 120 documents. Compared to awarded methods in the latest binarization contests, Sauvola's formula does not give the best results on historical documents. On the other hand, on clean magazines, it outperforms those methods. This implementation improves the robustness of Sauvola's algorithm by making the results almost insensible to the window size whatever the object sizes. Its properties make it usable in full document analysis toolchains. [ABSTRACT FROM AUTHOR]

Hierarchical hypercubes (HHC), also known as cube-connected cubes, have been introduced in the literature as an interconnection network for massively parallel systems. Effectively, they can connect a large number of nodes while retaining a small diameter and a low degree compared to a hypercube of the same size. Especially (2+ m)-dimensional hierarchical hypercubes ( $\mathit {HHC}_{2^{m}+m}$), called perfect HHCs, are popular as they are symmetrical, which is a critical property when designing routing algorithms. In this paper, we describe an algorithm finding, in an $\mathit{HHC}_{2^{m}+m}$, mutually node-disjoint paths connecting k=⌈( m+1)/2⌉ pairs of distinct nodes. This problem is known as the k-pairwise disjoint-path routing problem and is one of the important routing problems when dealing with interconnection networks. In an $\mathit{HHC}_{2^{m}+m}$, our algorithm finds paths of lengths at most 2+ m(2+1)+4 in O(2) time, where 2 is the diameter of an $\mathit{HHC}_{2^{m}+m}$. Also, we have shown through an experiment that, in practice, the lengths of the generated paths are significantly lower than the worst-case theoretical estimations. [ABSTRACT FROM AUTHOR]

The error linear complexity spectrum of a periodic sequence is defined to be the ordered list of $$k$$ k -error linear complexities of the sequence. In this paper, we present an algorithm which computes the error linear complexity spectrum for binary sequences with period $$p^{n}$$ p n , where $$p$$ p is an odd prime and $$2$$ 2 is a primitive root modulo $$p^{2}$$ p 2 . [ABSTRACT FROM AUTHOR]

The m-machine no-wait flowshop scheduling problem, with the objective of minimizing total completion time subject to the constraint that makespan has to be less than or equal to a certain value, is addressed in this paper. First, an algorithm is proposed to find an upper bound on the makespan in case the upper bound is not given or unknown. Given the upper bound on makespan, a proposed algorithm ( PAL) with five versions L (1, 5, 10, 15, and 20) and a genetic algorithm ( GA) are utilized for solving the problem. Furthermore, a dominance relation is established for the case of four machines. The five versions of PAL and GA are evaluated on randomly generated problems with different number of jobs and number of machines. Computational experiments show that the errors of PA10, PA15, and PA20 are much smaller than that of GA while the CPU times of PA10, PA15, and PA20 are significantly smaller than that of GA. Therefore, the algorithms PA10, PA15, and PA20 are superior to the GA algorithm. [ABSTRACT FROM AUTHOR]

Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O( n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists. [ABSTRACT FROM AUTHOR]

Continuous radon monitoring in soil and groundwater is one of the useful methods in earthquake prediction process. There are many published studies on geochemical precursors to seismic activity, both reporting the detection of validated precursory phenomena. The research on geochemical precursory algorithms is aimed at defining quantitative relations between seismogenic parameters and endogenetic components. This paper presents a new analytical algorithm that can be used to estimate optimum location and magnitude of coming earthquakes based on variations in radon concentration or any other geochemical precursors. In a real life application of this algorithm, radon monitoring network for Kerman province has been designed and the resulting data have been investigated. This practical example corroborates the proposed algorithm as well and the resulting seismogenic parameters e.g. location and magnitude have been obtained within their acceptable ranges. Furthermore, the proposed algorithm emphasizes on hot-springs which have the most effect on results around target zone. [ABSTRACT FROM AUTHOR]

An algorithm for finding the largest singular value of a nonnegative rectangular tensor was recently proposed by Chang, Qi, and Zhou [J. Math. Anal. Appl., 2010, 370: 284-294]. In this paper, we establish a linear convergence rate of the Chang-Qi-Zhou algorithm under a reasonable assumption. [ABSTRACT FROM AUTHOR]

Small Footprint LiDAR (Light Detection And Ranging) has been proposed as an effective tool for measuring detailed biophysical characteristics of forests over broad spatial scales. However, by itself LiDAR yields only a sample of the true 3D structure of a forest. In order to extract useful forestry relevant information, this data must be interpreted using mathematical models and computer algorithms that infer or estimate specific forest metrics. For these outputs to be useful, algorithms must be validated and/or calibrated using a sub-sample of 'known' metrics measured using more detailed, reliable methods such as field sampling. In this paper we describe a novel method for delineating and deriving metrics of individual trees from LiDAR data based on watershed segmentation. Because of the costs involved with collecting both LiDAR data and field samples for validation, we use synthetic LiDAR data to validate and assess the accuracy of our algorithm. This synthetic LiDAR data is generated using a simple geometric model of Loblolly pine ( Pinus taeda) trees and a simulation of LiDAR sampling. Our results suggest that point densities greater than 2 and preferably greater than 4 points per m2 are necessary to obtain accurate forest inventory data from Loblolly pine stands. However the results also demonstrate that the detection errors (i.e. the accuracy and biases of the algorithm) are intrinsically related to the structural characteristics of the forest being measured. We argue that experiments with synthetic data are directly useful to forest managers to guide the design of operational forest inventory studies. In addition, we argue that the development of LiDAR simulation models and experiments with the data they generate represents a fundamental and useful approach to designing, improving and exploring the accuracy and efficiency of LiDAR algorithms. [ABSTRACT FROM AUTHOR]

Multi-traveling salesman problem (MTSP) is an extension of traveling salesman problem, which is a famous NP hard problem, and can be used to solve many real world problems, such as railway transportation, routing and pipeline laying. In this paper, we analyze the general properties of MTSP, and find that the multiple depots and closed paths in the graph is a big issue for MTSP. Thus, a novel method is presented to solve it. We transform a complicated graph into a simplified one firstly, then an effective algorithm is proposed to solve the MTSP based on the simplified results. In addition, we also propose a method to optimize the general results by using 2-OPT. Simulation results show that our method can find the global solution for MTSP efficiently. [ABSTRACT FROM AUTHOR]

One of the critical limits on the sensitivity of direct neutrino mass experiment, such as MARE, is the background generated by unidentified double pulses. In our work developing an analysis system for MARE we have focused on comparing algorithms, and developing and testing an optimum algorithm for the identification (and removal) of double pulses. To test the algorithms we developed a Monte Carlo simulation that, based on the detectors physical parameters, generates realistic single and double events with known characteristics. In this paper we present our preliminary results on two algorithms used for double pulse identification and their efficiency as a function of pulse heights and separation. [ABSTRACT FROM AUTHOR]

Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are given integers such that 0≤ l≤ u. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such a partition is called an ( l, u)-partition. We deal with three problems to find an ( l, u)-partition of a given graph: the minimum partition problem is to find an ( l, u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and the p-partition problem is to find an ( l, u)-partition with a given number p of components. All these problems are NP-hard even for series-parallel graphs, but are solvable in linear time for paths. In this paper, we present the first polynomial-time algorithm to solve the three problems for arbitrary trees. [ABSTRACT FROM AUTHOR]

Background: Searching for substructures in molecules belongs to the most elementary tasks in cheminformatics and is nowadays part of virtually every cheminformatics software. The underlying algorithms, used over several decades, are designed for the application to general graphs. Applied on molecular graphs, little effort has been spend on characterizing their performance. Therefore, it is not clear how current substructure search algorithms behave on such special graphs. One of the main reasons why such an evaluation was not performed in the past was the absence of appropriate data sets. Results: In this paper, we present a systematic evaluation of Ullmann's and the VF2 subgraph isomorphism algorithms on molecular data. The benchmark set consists of a collection of 1235 SMARTS substructure expressions and selected molecules from the ZINC database. The benchmark evaluates substructures search times for complete database scans as well as individual substructure-molecule pairs. In detail, we focus on the influence of substructure formulation and size, the impact of molecule size, and the ability of both algorithms to be used on multiple cores. Conclusions: The results show a clear superiority of the VF2 algorithm in all test scenarios. In general, both algorithms solve most instances in less than one millisecond, which we consider to be acceptable. Still, in direct comparison, the VF2 is most often several folds faster than Ullmann's algorithm. Additionally, Ullmann's algorithm shows a surprising number of run time outliers. [ABSTRACT FROM AUTHOR]

The ASEDRA (Advanced Synthetically Enhanced Detector Resolution Algorithm, patent pending) has been successfully applied as a post processing algorithm to both sodium iodide (NaI(Tl)) and cesium iodide (CsI(Na)) scintillator detectors to synthetically enhance their realized spectral data resolution by as much as a factor of three, wherein from these detectors the 'raw' unprocessed spectra are traditionally of poor resolution. ASEDRA uses noise reduction and built-in high resolution Monte Carlo radiation transport based detector response functions (DRFs) to rapidly post-process a spectrum in a few seconds on a standard laptop; gamma lines are extracted with an accuracy that makes the scintillator detectors competitive with higher resolution, higher material cost detectors. ASEDRA differs from other tools in the field, such as Sandia's GADRAS software, in that ASEDRA performs a differential spectrum attribution and cumulative extraction from the sample spectrum, rather than an integral-based approach, as in GADRAS. Previous publications have highlighted the successful application of ASEDRA in samples with plutonium and various isotopes. A new SmartID nuclide identification package to accompany ASEDRA has recently been implemented for test and evaluation purposes for sample attribution; in addition, the application of ASEDRA+SmartID has occurred with success in long dwell cargo monitoring and SNM detection applications, enabling new protocols for HEU detection. Overall, this paper presents recent developments and results along with a discussion of follow-on steps in the development of ASEDRA as an effective field gamma spectrum analysis tool for low cost scintillators. [ABSTRACT FROM AUTHOR]

We consider a generalization of the well-known domination problem on graphs. The ( soft) capacitated domination problem with demand constraints is to find a dominating set D of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demands of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies the demand of each vertex in V to be met by the capacities of vertices in D dominating it. In this paper, we study the capacitated domination problem on trees from an algorithmic point of view. We present a linear time algorithm for the unsplittable demand model, and a pseudo-polynomial time algorithm for the splittable demand model. In addition, we show that the capacitated domination problem on trees with splittable demand constraints is NP-complete (even for its integer version) and provide a polynomial time approximation scheme (PTAS). We also give a primal-dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs. [ABSTRACT FROM AUTHOR]

In the next decade, the high-performance supercomputers will consist of several millions of CPUs. The interconnection networks in such supercomputers play an important role for achieving high performance. In this paper, we introduce the Metacube (MC), a versatile family of interconnection network that can connect an extremely large number of nodes with a small number of links per node and keep the diameter rather low. An MC network has a 2-level hypercube structure. An MC( k, m) network can connect $2^{2^{k}m+k}$ nodes with m+ k links per node, where k is the dimension of the high-level hypercubes (classes) and m is the dimension of the low-level hypercubes (clusters). An MC is a symmetric network with short diameter, easy and efficient routing and broadcasting similar to that of the hypercube. However, the MC network can connect millions of nodes with up to 6 links per node. An MC(2,3) with 5 links per node has 16,384 nodes and an MC(3,3) with 6 links per node has 134,217,728 nodes. We describe the MC network’s structure, topological properties, routing and broadcasting algorithms, and the Hamiltonian cycle embedding in the Metacube networks. [ABSTRACT FROM AUTHOR]

In this paper, we present and analyze a fast algorithm that determines the possible molecular formulae corresponding to the resolved peaks in the spectral data obtained from a mass analyzer like an FT-ICR-MS. In contrast to our approach, most known algorithms and software that attempt to solve this important problem are brute-force in nature and consequently, highly prone to combinatorial explosion when dealing with the volume of real data. We also present an object-oriented implementation of our algorithm in a general-purpose, user-friendly, interactive, and easily extensible software tool PG C ompound M atch F inder. A run-time performance analysis of our software shows that even when dealing with several billion theoretical possibilities matched against tens of thousands of resolved peaks, a complete analysis using today’s standard desktop machines can take only a few minutes. [ABSTRACT FROM AUTHOR]