Search

Wireless Body Area Networks (WBANs) are critical in medical emergency services within the Internet of Things (IoT). Ensuring efficient channel utilization while avoiding collisions and optimizing route allocation is a significant research focus in this field. However, the existing CSMA/CA methods need help updating the contention window and achieving fair node distribution. This paper proposes a novel Prime number-based Backoff Counter Adjustment (PBCA) strategy to address this issue. The PBCA algorithm dynamically adjusts the contention window based on the success counter and the prime backoff stages (BS). A mathematical analysis of the proposed PBCA algorithm uses Discrete-Time Markov Chains to study its impact on saturated throughput and collision probability. The proposed algorithm simulation experiments demonstrate the superiority of the PBCA algorithm over existing approaches. The proposed strategy significantly enhances throughput, reduces packet loss and delay, and ensures the reliability of the WBAN network. Compared to existing algorithms, the PBCA algorithm optimizes 48.1% in throughput, 39.47% in packet loss, 45.11% in delay, and 78.62% in reliability. These results outstand the performance of the existing algorithms. This advancement holds promise for enhancing performance and reliability in medical emergency services within IoT applications. The future extension of this work involves integrating reinforcement learning techniques to assess network status accurately, enabling adaptive and intelligent channel allocation in wireless body area networks. [ABSTRACT FROM AUTHOR]

In cognitive radio networks (CRNs), rendezvous is the vital step prior to the communication between two unlicensed secondary users (SUs), where the SUs hop on the same channel at the same time to establish a link. With the dramatic fall in the cost and size of wireless transceivers, it becomes more reasonable to apply multiple radios to achieve significant improvement in the rendezvous performance. However, most of the existing multiradio rendezvous algorithms are proposed for homogeneous CRNs where all the SUs are equipped with an equal number of radios and do not possess backward compatibility to SU with a single radio. In reality, the CRNs are heterogeneous in nature as SUs may have different numbers of radios. In this paper, a composite CH algorithm is proposed for an asynchronous and heterogeneous network to achieve blind rendezvous with full rendezvous diversity. An SU with m number radios are categorized into three groups those follow different channel hopping (CH) algorithms. The upper bound of the rendezvous latency is being evaluated with a brief theoretical and mathematical analysis. Extensive simulations have conducted for different performance metrics, and the results are compared with the state-of-art algorithms. Overall, the proposed algorithm shows better performance in heterogeneous CRNs. [ABSTRACT FROM AUTHOR]

In the ensemble feature selection method, if the weight adjustment is performed on each feature subset used, the ensemble effect can be significantly different; therefore, how to find the optimized weight vector is a key and challenging problem. Aiming at this optimization problem, this paper proposes an ensemble feature selection approach based on genetic algorithm (EFS-BGA). After each base feature selector generates a feature subset, the EFS-BGA method obtains the optimized weight of each feature subset through genetic algorithm, which is different from traditional genetic algorithm directly processing single features. We divide the EFS-BGA algorithm into two types. The first is a complete ensemble feature selection method; based on the first, we further propose the selective EFS-BGA model. After that, through mathematical analysis, we theoretically explain why weight adjustment is an optimization problem and how to optimize. Finally, through the comparative experiments on multiple data sets, the advantages of the EFS-BGA algorithm in this paper over the previous ensemble feature selection algorithms are explained in practice. [ABSTRACT FROM AUTHOR]

The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a non-negative monotone submodular function f:Z+n→R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Given this, we design polynomial-time (1-1/e-ϵ)-approximation algorithms for a cardinality constraint, a polymatroid constraint, and a knapsack constraint. For a cardinality constraint, we also provide a (1-1/e-ϵ)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property. [ABSTRACT FROM AUTHOR]

Virtual machine (VM) placement is a fundamental problem about resource scheduling in cloud computing; however, the design and implementation of an efficient VM placement algorithm are very challenging. To better multiplex and share physical hosts in the cloud data centers, this paper presents a VM placement algorithm based on the peak workload characteristics, which models the workload characteristics of VMs with mathematical method, and measures the similarity of VMs' workload with VM peak similarity. Avoiding virtual machines whose workload has high correlation are placed together, it places the virtual machines with peak workload staggering at different time together, which achieves better VM consolidation through VM peak similarity. This paper focuses on the mathematical analysis of VM peak similarity, and proves that compared to cosine-similarity method and correlation-coefficient method, peak-similarity method is better theoretically. Finally, numerical simulations and algorithm experiments show that our proposed peak-similarity-based placement algorithm outperforms the random placement algorithm and correlation-coefficient-based placement algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we present a refinement of the Cipolla-Lehmer type algorithm given by H. C. Williams in 1972, and later improved by K. S. Williams and K. Hardy in 1993. For a given r-th power residue c∈Fq where r is an odd prime, the algorithm of H. C. Williams determines a solution of Xr=c in O(r3logq) multiplications in Fq, and the algorithm of K. S. Williams and K. Hardy finds a solution in O(r4+r2logq) multiplications in Fq. Our refinement finds a solution in O(r3+r2logq) multiplications in Fq. Therefore our new method is better than the previously proposed algorithms independent of the size of r, and the implementation result via SageMath shows a substantial speed-up compared with the existing algorithms. It should be mentioned that our method also works for a composite r. [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]

The direct problem of simple geometrical bodies plays an important role in the gravimetrical processing and modelling tools. We focused on the 3D rectangular prism, which is widely used in such processes. Even though the solution for this body is well known, there are still some issues about it, which are not answered or not answered completely in the available literature, e.g. the presence of the singularities in the source-free points or a continuity of the solutions. We present the singularity-free solution valid for the each position of the calculation point. Next, the analysis of the two basic types of the formulae for the 3D rectangular prism's gravitational effect is held on. We discuss the ways of their derivation, the validity and the problems connected with them. Later, special attention is paid at the problems with the citation of these two formulae types within the gravimetrical literature. [ABSTRACT FROM AUTHOR]

The classical method for program analysis by abstract interpretation consists in computing first an increasing sequence using an extrapolation operation, called widening, to correctly approximate the limit of the sequence. Then, this approximation is improved by computing a decreasing sequence without widening, the terms of which are all correct, more and more precise approximations. It is generally admitted that, when the decreasing sequence reaches a fixpoint, it cannot be improved further. As a consequence, most efforts for improving the precision of an analysis have been devoted to improving the limit of the increasing sequence. In a previous paper, we proposed a method to improve a fixpoint after its computation. This method consists in computing from the obtained solution a new starting value from which increasing and decreasing sequences are computed again. The new starting value is obtained by projecting the solution onto well-chosen components. The present paper extends and improves the previous paper: the method is discussed in view of some example programs for which it fails. A new method is proposed to choose the restarting value: the restarting value is no longer a simple projection, but is built by gathering and combining information backward the widening nodes in the basic solution. Experiments show that the new method properly solves all our examples, and improves significantly the results obtained on a classical benchmark. [ABSTRACT FROM AUTHOR]

This paper presents a GPU-accelerated implementation of an image encryption algorithm. The algorithm uses the concepts of a modified XOR cipher to encrypt and decrypt the images, with an encryption pad, generated using the shared secret key and some initialization vectors. It uses a genetically optimized pseudo-random generator that outputs a stream of random bytes of the specified length. The proposed algorithm is subjected to a number of theoretical, experimental, and mathematical analyses, to examine its performance and security against a number of possible attacks, using the following metrics - histogram analysis, correlation analysis, information entropy analysis, NPCR and UACI. The performance analysis carried out shows an average speedup-ratio of 3.489 for encryption, and 4.055 for decryption operation, between the serial and parallel implementations using GPU. The algorithm aims to provide better performance benchmarks, which can significantly improve the experience in the relevant use-cases, like real-time media applications. [ABSTRACT FROM AUTHOR]

Robust analysis is important for designing and analyzing algorithms for global optimization. In this paper, we introduce a new concept, robust constant, to quantitatively characterize the robustness of measurable sets and functions. The new concept is consistent to the theoretical robustness presented in literatures. This paper shows that, from the respects of convergence theory and numerical computational cost, robust constant is valuable significantly for analyzing random global search methods for unconstrained global optimization. [ABSTRACT FROM AUTHOR]

It has been pointed out by Jones D. R. that the DIRECT global optimization algorithm can quickly get close to the basin of the optimum but takes longer to achieve a high degree of accuracy. In this paper, we introduce a bilevel strategy into a modifed DIRECT algorithm to overcome this shortcoming. The proposed algorithm is proved to be convergent globally. Numerical results show that the proposed algorithm is very promising. [ABSTRACT FROM AUTHOR]

In this paper, we prove that for a linearly ordered skewfield the groups of quotients of the semigroup Gn(픻) coincides with the group GLn(픻) for n ≥ 3. [ABSTRACT FROM AUTHOR]

In this paper we consider large fixed point problems and solution with proximal algorithms. We show that for linear problems there is a close connection between proximal iterations, which are prominent in numerical analysis and optimization, and multistep methods of the temporal difference type such as TD(λ), LSTD(λ), and LSPE(λ), which are central in simulation-based exact and approximate dynamic programming. One benefit of this connection is a new and simple way to accelerate the standard proximal algorithm by extrapolation towards a multistep iteration, which generically has a faster convergence rate. Another benefit is the potential for integration into the proximal algorithmic context of several new ideas that have emerged in the approximate dynamic programming context, including simulation-based implementations. Conversely, the analytical and algorithmic insights from proximal algorithms can be brought to bear on the analysis and the enhancement of temporal difference methods. We also generalize our linear case result to nonlinear problems that involve a contractive mapping, thus providing guaranteed and potentially substantial acceleration of the proximal and forward backward splitting algorithms at no extra cost. Moreover, under certain monotonicity assumptions, we extend the connection with temporal difference methods to nonlinear problems through a linearization approach. [ABSTRACT FROM AUTHOR]

Bayesian optimization has become a widely used tool in the optimization and machine learning communities. It is suitable to problems as simulation/optimization and/or with an objective function computationally expensive to evaluate. Bayesian optimization is based on a surrogate probabilistic model of the objective whose mean and variance are sequentially updated using the observations and an “acquisition” function based on the model, which sets the next observation at the most “promising” point. The most used surrogate model is the Gaussian Process which is the basis of well-known Kriging algorithms. In this paper, the authors consider the pump scheduling optimization problem in a Water Distribution Network with both ON/OFF and variable speed pumps. In a global optimization model, accounting for time patterns of demand and energy price allows significant cost savings. Nonlinearities, and binary decisions in the case of ON/OFF pumps, make pump scheduling optimization computationally challenging, even for small Water Distribution Networks. The well-known EPANET simulator is used to compute the energy cost associated to a pump schedule and to verify that hydraulic constraints are not violated and demand is met. Two Bayesian Optimization approaches are proposed in this paper, where the surrogate model is based on a Gaussian Process and a Random Forest, respectively. Both approaches are tested with different acquisition functions on a set of test functions, a benchmark Water Distribution Network from the literature and a large-scale real-life Water Distribution Network in Milan, Italy. [ABSTRACT FROM AUTHOR]

In this paper, we introduce an algorithm for presentation of an inner estimation of the solution set of a complex interval linear system, where the coefficient matrix is a crisp complex-valued matrix and the right-hand-side vector is an interval complex-valued vector. Also, we show that under some certain conditions, the obtained inner estimation is, in fact, an algebraic solution. [ABSTRACT FROM AUTHOR]

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 proposes an efficiency quantum image steganography protocol based on improved exploiting modification direction algorithm (QIS-IEMD). The new methods of expanding modification range and dynamically sharing between subgroups are introduced in the new protocol. Compared with the quantum image steganography protocol based on EMD algorithm (QIS-EMD), secret information can be embedded on multiple bit planes after expanding pixel's modification range, and the carrier pixel groups can be dynamically shared to achieve higher embedding efficiency, embedding rate and larger capacity. In addition, in order to reflect the feasibility and practicability of QIS-IEMD, dedicated quantum circuits for embedding and extracting secret information are designed for it. Finally, the experimental results and detailed mathematical analysis prove that, compared with QIS-EMD, QIS-IEMD not only performs well in imperceptibility, but also significantly increases embedding efficiency, embedding rate and capacity. [ABSTRACT FROM AUTHOR]

An improved particle swarm optimization algorithm based on the model of refracting opposite learning, called refrPSO, is applied to design and optimize FIR low pass and high pass digital filters with linear phase. According to the refraction principle of light, the process of opposition-based learning is ameliorated, and then a new model of opposition-based learning, which is applied for improvement of particle swarm optimization, is proposed. For enhancing the performance of FIR digital filters, in this paper, the optimal combination of the filter coefficients is found out by applying the refrPSO for the design of FIR digital filters. Meanwhile, some well-known algorithms such as classic Parks-McClellan, standard Particle Swarm optimization and Particle Swarm optimization based on opposite learning are used to design FIR digital filters for comparison. Extensive experimental results show that the performance of FIR digital filters optimized by the refrPSO outperforms the one optimized by other algorithms obviously. [ABSTRACT FROM AUTHOR]

In this paper, we propose an improved quantum algorithm for the minimum mean square error-based massive multiple-input multiple-output (MIMO) uplink. The new algorithm can reduce the dependency on the assumptions on the input vector, the channel matrix entries and the low rank of the channel matrix, which are indispensable in our previous results. Our improved quantum algorithm applies the quantum block-encoding technology, which depends on the quantum-accessible data structure. Moreover, we design an efficient algorithm for outputting classical data, which makes sure that output data can be utilized in classical devices. Both theoretically mathematical analyses and simulation realizations in massive MIMO systems confirm the applicability of the improved quantum algorithm. With desired precision, and theoretical and numerical analysis, our improved quantum algorithm can achieve a quadratic or even an exponential speedup over classical counterparts. [ABSTRACT FROM AUTHOR]

The global BiCGSTAB (Gl-BiCGSTAB) method has been found to perform very well in many practical cases. However, like the BiCGSTAB method, it often converges slowly or stagnates for some non-symmetric linear systems with complex spectrum. In this paper, we propose a new global generalized product-type method based on the global BiCG (Gl-BCG) method to try and remedy these problems. To enhance stability of convergence and robustness, we also consider a variant of the new method based on minimization of the associate residual of F-norm and ascending order recurrence in place of reconstruction of the algorithm. Finally, numerical experiments are given to show that our methods can be more effective than the original methods. [ABSTRACT FROM AUTHOR]

In this paper, we show how the GHZ paradox can be used to design a computing device that cannot be physically implemented within the context of classical physics, but nonetheless can be within quantum physics, i.e., in a quantum physics laboratory. This example gives an illustration of the many subtleties involved in the quantum control of distributed quantum systems. We also show how the second elementary symmetric Boolean function can be interpreted as a quantification of the nonlocality and indeterminism involved in the GHZ paradox. [ABSTRACT FROM AUTHOR]

Abstract. This paper deals with an extremal problem concerning hypergraph colorings. Let k be an integer. The problem is to find the value m( n) equal to the minimum number of edges in an n-uniform hypergraph not admitting two-colorings of the vertex set such that every edge of the hypergraph contains at least k vertices of each color. In this paper, we obtain upper bounds of m( n) for small k and n, the exact value of m(8), and a lower bound for m(7). [ABSTRACT FROM AUTHOR]

In this paper, the investigation of groups with additional finiteness conditions is continued. Criteria of residual finiteness and of almost local solvability of a periodic F* -group are obtained. [ABSTRACT FROM AUTHOR]

As the use of wireless sensor networks increases, the need for efficient and reliable broadcasting algorithms grows. Ideally, a broadcasting algorithm should have the ability to quickly disseminate data, while keeping the number of transmissions low. In this paper, we analyze the popular Trickle algorithm, which has been proposed as a suitable communication protocol for code maintenance and propagation in wireless sensor networks. We show that the broadcasting process of a network using Trickle can be modeled by a Markov chain and that this chain falls under a class of Markov chains, closely related to residual lifetime distributions. It is then shown that this class of Markov chains admits a stationary distribution of a special form. These results are used to analyze the Trickle algorithm and its message count. Our results prove conjectures made in the literature concerning the effect of a listen-only period. Besides providing a mathematical analysis of the algorithm, we propose a generalized version of Trickle, with an additional parameter defining the length of a listen-only period. [ABSTRACT FROM AUTHOR]

Color constancy is a problem of hard solution, and most of existing theories are applied only to synthesized images, while others present a limited performance when applied to real images. In this paper, we apply and analyze a color constancy algorithm that is used with real images subjected to sudden changes in illumination, both in outdoor and indoor environments. In this algorithm, by knowing the colors of some points on the scene submitted to a standard illumination, scene image color correction is made so that it appears always to be under the standard illumination influence. The method employed in this paper is applied to some tasks, such as tracking colored targets, controlling a robot using visual information and pre-processing outdoor images to help on place characterization. Moreover, the algorithm implemented in this work is camera independent because it does not depend on the camera-sensitive responses. The only requirement is that the camera responses can be approximated by the CIE XYZ $$2^o$$ standard observer functions. The experimental results are discussed and analyzed in order to evaluate the performance of the color constancy method. [ABSTRACT FROM AUTHOR]

In this paper, we present the first full regions-and-effects inference algorithm for explicitly parallel fork-join programs. We infer annotations equivalent to those in Deterministic Parallel Java (DPJ) for type-safe C++ programs. We chose the DPJ annotations because they give the strongest safety guarantees of any existing concurrency-checking approach we know of, static or dynamic, and it is also the most expressive static checking system we know of that gives strong safety guarantees. This expressiveness, however, makes manual annotation difficult and tedious, which motivates the need for automatic inference, but it also makes the inference problem very challenging: the code may use region polymorphism, imperative updates with complex aliasing, arbitrary recursion, hierarchical region specifications, and wildcard elements to describe potentially infinite sets of regions. We express the inference as a constraint satisfaction problem and develop, implement, and evaluate an algorithm for solving it. The region and effect annotations inferred by the algorithm constitute a checkable proof of safe parallelism, and it can be recorded both for documentation and for fast and modular safety checking. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new hierarchy of large cardinals between I3 and I2, the iterability hierarchy, and we prove that every step of it strongly implies the ones below. [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]

In this paper, we introduce and study a new coloring problem of a graph called the dominated coloring. A dominated coloring of a graph $$G$$ is a proper vertex coloring of $$G$$ such that each color class is dominated by at least one vertex of $$G$$ . The minimum number of colors among all dominated colorings is called the dominated chromatic number, denoted by $$\chi _{dom}(G)$$ . In this paper, we establish the close relationship between the dominated chromatic number $$\chi _{dom}(G)$$ and the total domination number $$\gamma _t(G)$$ ; and the equivalence for triangle-free graphs. We study the complexity of the problem by proving its NP-completeness for arbitrary graphs having $$\chi _{dom}(G) \ge 4$$ and by giving a polynomial time algorithm for recognizing graphs having $$\chi _{dom}(G) \le 3$$ . We also give some bounds for planar and star-free graphs and exact values for split graphs. [ABSTRACT FROM AUTHOR]

This paper deals with equilibrium problems with nonlinear constraints. Exploiting a gap function which relies on a polyhedral approximation of the feasible region, we propose two descent methods. They are both based on the minimization of a suitable exact penalty function, but they use different rules for updating the penalization parameter and they rely on different types of line search. The convergence of both algorithms is proved under standard assumptions. [ABSTRACT FROM AUTHOR]

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held-Karp relaxation, which may be of independent interest. [ABSTRACT FROM AUTHOR]

Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro. [ABSTRACT FROM AUTHOR]

Many evolutionary multi-objective optimization (EMO) methodologies have been proposed and performed very well on finding a representative set of Pareto-optimal solutions, but this advantage will be weakened with the increasing number of objectives. And in real applications, what decision makers (DMs) want is a unique solution or a set of solutions rather than the overall Pareto-optimal front. It is a difficult task to solve many-objective problems by using preference information provided by decision maker (DM) during optimization process. In this paper, a new angle-based preference selection mechanism is proposed, which replaces the traditional crowding distance with the aid of preference information provided by the DMs. Particularly, we combine it with a multi-objective immune algorithm with non-dominated neighbor-based selection. The proposed method has been extensively compared with other recently proposed preference-based EMO approaches over DTLZ1, DTLZ2, and DTLZ3 test problems with 4-100 objectives. The results of the experiment indicate that the proposed algorithm can achieve competitive and better results. [ABSTRACT FROM AUTHOR]

Copyright of Arabian Journal for Science & Engineering (Springer Science & Business Media B.V. ) is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In this paper we explore the construction of arbitrarily tight αBB relaxations of C2 general non-linear non-convex functions. We illustrate the theoretical challenges of building such relaxations by deriving conditions under which it is possible for an αBB underestimator to provide exact bounds. We subsequently propose a methodology to build αBB underestimators which may be arbitrarily tight (i.e., the maximum separation distance between the original function and its underestimator is arbitrarily close to 0) in some domains that do not include the global solution (defined in the text as “sub-optimal”), assuming exact eigenvalue calculations are possible. This is achieved using a transformation of the original function into a μ-subenergy function and the derivation of αBB underestimators for the new function. We prove that this transformation results in a number of desirable bounding properties in certain domains. These theoretical results are validated in computational test cases where approximations of the tightest possible μ-subenergy underestimators, derived using sampling, are compared to similarly derived approximations of the tightest possible classical αBB underestimators. Our tests show that μ-subenergy underestimators produce much tighter bounds, and succeed in fathoming nodes which are impossible to fathom using classical αBB. [ABSTRACT FROM AUTHOR]

We study the Nesting Problem, which aims to determine a configuration of a set of irregular shapes within a rectangular sheet of material of fixed width, such that no overlap among the shapes exists, and such that the length of the sheet is minimized. When both translation and rotation of the shapes are allowed, the problem can be formulated as a nonconvex quadratically constrained programming model that approximates each shape by a set of inscribed circles and enforces that circle pairs stemming from different shapes do not overlap. However, despite many recent advances in today’s global optimization solvers, solving this nonconvex model to guaranteed optimality remains extremely challenging even for the state-of-the-art codes. In this paper, we propose a customized branch-and-bound approach to address the Nesting Problem to guaranteed optimality. Our approach utilizes a novel branching scheme to deal with the reverse convex quadratic constraints in the quadratic model and incorporates a number of problem-specific algorithmic tweaks. Our computational studies on a suite of 64 benchmark instances demonstrate the customized algorithm’s effectiveness and competitiveness over the use of general-purpose global optimization solvers, including for the first time the ability to find global optimal nestings featuring five polygons under free rotation. [ABSTRACT FROM AUTHOR]

In this paper we propose a nonlinear Generalized Disjunctive Programming model to optimize the 2-dimensional continuous location and allocation of the potential facilities based on their maximum capacity and the given coordinates of the suppliers and customers. The model belongs to the class of Capacitated Multi-facility Weber Problem. We propose a bilevel decomposition algorithm that iteratively solves a discretized MILP version of the model, and its nonconvex NLP for a fixed selection of discrete variables. Based on the bounding properties of the subproblems, ϵ-convergence is proved for this algorithm. We apply the proposed method to random instances varying from 2 suppliers and 2 customers to 40 suppliers and 40 customers, from one type of facility to 3 different types, and from 2 to 32 potential facilities. The results show that the algorithm is more effective at finding global optimal solutions than general purpose global optimization solvers tested. [ABSTRACT FROM AUTHOR]

On the provable security of a block cipher against impossible differential cryptanalysis, the maximal length of impossible differentials is an essential aspect. Most previous work on finding impossible differentials for AES, omits the non-linear component (S-box), which is important for the security. In EUROCRYPT 2016, Sun et al. showed how to bound the length of impossible differentials of a SPN “structure” using the primitive index of its linear layer. They proved that there do not exist impossible differentials longer than four rounds for the AES “structure”, instead of the AES cipher. Since they do not consider the details of the S-box, their bound is not feasible for a concrete cipher. With their result, the upper bound of the length of impossible differentials for AES, is still unknown. We fill this gap in our paper. By revealing some important properties of the AES S-box, we further prove that even though the details of the S-box are considered, there do not exist truncated impossible differentials covering more than four rounds for AES, under the assumption that round keys are independent and uniformly random. Specially, even though the details of the S-box and key schedule are both considered, there do not exist truncated impossible differentials covering more than four rounds for AES-256. [ABSTRACT FROM AUTHOR]

In this paper, we present an algorithm which can prove algebraic relations involving η -quotients, where η is the Dedekind eta function. [ABSTRACT FROM AUTHOR]

This paper proposes an efficient method for solving complex multicriterial optimization problems, for which the optimality criteria may be multiextremal and the calculations of the criteria values may be time-consuming. The approach involves reducing multicriterial problems to global optimization ones through minimax convolution of partial criteria, reducing dimensionality by using Peano curves and implementing efficient information-statistical methods for global optimization. To efficiently find the set of Pareto-optimal solutions, it is proposed to reuse all the search information obtained in the course of optimization. The results of computational experiments indicate that the proposed approach greatly reduces the computational complexity of solving multicriterial optimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider solving a set of global optimization problems in parallel. The proposed novel algorithm provides uniform convergence to the set of solutions for all problems treated simultaneously. The current accuracy for each particular solution is estimated by the difference in each coordinate from the point of global decision. The main statement is given in the corresponding theorem. For the sake of illustration some computational results with hundreds of multidimensional global problems are provided. [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]

The nonmonotone globalization technique is useful in difficult nonlinear problems, because of the fact that it may help escaping from steep sided valleys and may improve both the possibility of finding the global optimum and the rate of convergence. This paper discusses the nonmonotonicity degree of nonmonotone line searches for the unconstrained optimization. Specifically, we analyze some popular nonmonotone line search methods and explore, from a computational point of view, the relations between the efficiency of a nonmonotone line search and its nonmonotonicity degree. We attempt to answer this question how to control the degree of the nonmonotonicity of line search rules in order to reach a more efficient algorithm. Hence in an attempt to control the nonmonotonicity degree, two adaptive nonmonotone rules based on the morphology of the objective function are proposed. The global convergence and the convergence rate of the proposed methods are analysed under mild assumptions. Numerical experiments are made on a set of unconstrained optimization test problems of the CUTEr (Gould et al. in ACM Trans Math Softw 29:373-394, 2003) collection. The performance data are first analysed through the performance profile of Dolan and Moré (Math Program 91:201-213, 2002). In the second kind of analyse, the performance data are analysed in terms of increasing dimension of the test problems. [ABSTRACT FROM AUTHOR]

This paper presents a coercive smoothed penalty framework for nonsmooth and nonconvex constrained global optimization problems. The properties of the smoothed penalty function are derived. Convergence to an $$\varepsilon $$ -global minimizer is proved. At each iteration k, the framework requires the $$\varepsilon ^{(k)}$$ -global minimizer of a subproblem, where $$\varepsilon ^{(k)} \rightarrow \varepsilon $$ . We show that the subproblem may be solved by well-known stochastic metaheuristics, as well as by the artificial fish swarm (AFS) algorithm. In the limit, the AFS algorithm convergence to an $$\varepsilon ^{(k)}$$ -global minimum of the real-valued smoothed penalty function is guaranteed with probability one, using the limiting behavior of Markov chains. In this context, we show that the transition probability of the Markov chain produced by the AFS algorithm, when generating a population where the best fitness is in the $$\varepsilon ^{(k)}$$ -neighborhood of the global minimum, is one when this property holds in the current population, and is strictly bounded from zero when the property does not hold. Preliminary numerical experiments show that the presented penalty algorithm based on the coercive smoothed penalty gives very competitive results when compared with other penalty-based methods. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of simulating multivariate random fields with stationary Gaussian increments in a d-dimensional Euclidean space. To this end, one considers a spectral turning-bands algorithm, in which the simulated field is a mixture of basic random fields made of weighted cosine waves associated with random frequencies and random phases. The weights depend on the spectral density of the direct and cross variogram matrices of the desired random field for the specified frequencies. The algorithm is applied to synthetic examples corresponding to different spatial correlation models. The properties of these models and of the algorithm are discussed, highlighting its computational efficiency, accuracy and versatility. [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]

In this paper, a parametric simplex algorithm for solving linear vector optimization problems (LVOPs) is presented. This algorithm can be seen as a variant of the multi-objective simplex (the Evans-Steuer) algorithm (Math Program 5(1):54-72, 1973). Different from it, the proposed algorithm works in the parameter space and does not aim to find the set of all efficient solutions. Instead, it finds a solution in the sense of Löhne (Vector optimization with infimum and supremum. Springer, Berlin, 2011), that is, it finds a subset of efficient solutions that allows to generate the whole efficient frontier. In that sense, it can also be seen as a generalization of the parametric self-dual simplex algorithm, which originally is designed for solving single objective linear optimization problems, and is modified to solve two objective bounded LVOPs with the positive orthant as the ordering cone in Ruszczyński and Vanderbei (Econometrica 71(4):1287-1297, 2003). The algorithm proposed here works for any dimension, any solid pointed polyhedral ordering cone C and for bounded as well as unbounded problems. Numerical results are provided to compare the proposed algorithm with an objective space based LVOP algorithm [Benson's algorithm in Hamel et al. (J Global Optim 59(4):811-836, 2014)], that also provides a solution in the sense of Löhne (2011), and with the Evans-Steuer algorithm (1973). The results show that for non-degenerate problems the proposed algorithm outperforms Benson's algorithm and is on par with the Evans-Steuer algorithm. For highly degenerate problems Benson's algorithm (Hamel et al. 2014) outperforms the simplex-type algorithms; however, the parametric simplex algorithm is for these problems computationally much more efficient than the Evans-Steuer algorithm. [ABSTRACT FROM AUTHOR]

The doubling algorithms are very efficient iterative methods for computing the unique minimal nonnegative solution to an M-matrix algebraic Riccati equation (MARE). They are globally and quadratically convergent, except for MARE in the critical case where convergence is linear with the linear rate 1 / 2. However, the initialization phase and the doubling iteration kernel of any doubling algorithm involve inverting nonsingular M-matrices. In particular, for MARE in the critical case, the M-matrices in the doubling iteration kernel, although nonsingular, move towards singular M-matrices at convergence. These inversions are causes of concerns on entrywise relative accuracy of the eventually computed minimal nonnegative solution. Fortunately, a nonsingular M-matrix can be inverted by the GTH-like algorithm of Alfa et al. (Math Comp 71:217-236, 2002) to almost full entrywise relative accuracy, provided a triplet representation of the matrix is known. Recently, Nguyen and Poloni (Numer Math 130(4):763-792, 2015) discovered a way to construct triplet representations in a cancellation-free manner for all involved M-matrices in the doubling iteration kernel, for a special class of MAREs arising from Markov-modulated fluid queues. In this paper, we extend Nguyen's and Poloni's work to all MAREs by also devising a way to construct the triplet representations cancellation-free. Our construction, however, is not a straightforward extension of theirs. It is made possible by an introduction of novel recursively computable auxiliary nonnegative vectors. As the second contribution, we propose an entrywise relative residual for an approximate solution. The residual has an appealing feature of being able to reveal the entrywise relative accuracies of all entries, large and small, of the approximation. This is in marked contrast to the usual legacy normalized residual which reflects relative accuracies of large entries well but not so much those of very tiny entries. Numerical examples are presented to demonstrate and confirm our claims. [ABSTRACT FROM AUTHOR]

In this work, we focus on building an efficient succinct dynamic dictionary that significantly improves the query time of the current best known results. The algorithm that we propose suffers from only a $$ O((\log \log n)^2 )$$ multiplicative slowdown in its query time and a $$O(\frac{1}{\epsilon } \log n)$$ slowdown for insertion and deletion operations, where n is the sum of all of the patterns' lengths, the size of the alphabet is $$\textit{polylog}(n)$$ and $$\epsilon \in (0,1)$$ . For general alphabet the query time is $$ O((\log \log n) \log \sigma )$$ , where $$\sigma $$ is the size of the alphabet. A byproduct of this paper is an Aho-Corasick automaton that can be constructed with only a compact working space, which is the first of its type to the best of our knowledge. [ABSTRACT FROM AUTHOR]