Search

Symmetry is an important principle and characteristic that is prevalent in nature and artificial environments. In the three-dimensional packing problem, leveraging the inherent symmetry of goods and the symmetry of the packing space can enhance packing efficiency and utilization.The three-dimensional packing problem is an NP-hard combinatorial optimization problem in the field of modern logistics, with high computational complexity. This paper proposes an improved genetic algorithm by incorporating a fusion tabu search strategy to address this problem. The algorithm employs a three-dimensional loading mathematical model and utilizes a wall-building method under residual space constraints for stacking goods. Furthermore, adaptation of fitness variation strategy, chromosome adjustment, and tabu search algorithm are introduced to balance the algorithm's global and local search capabilities, as well as to enhance population diversity and convergence speed. Through testing on benchmark cases such as Bischoff and Ratcliff, the improved algorithm demonstrates an average increase of over 3% in packing space utilization compared to traditional genetic algorithms and other heuristic algorithms, validating its feasibility and effectiveness. The proposed improved genetic algorithm provides new insights for solving three-dimensional packing problems and optimizing logistics loading schedules, offering promising prospects for various applications. [ABSTRACT FROM AUTHOR]

Let p be an odd prime and Zp the residue class ring modulo p. In this paper, we study representations of any element of Zp as the sum of a Lehmer number and a primitive root in Zp, and give an explicit inequality better than asymptotic formula for the number of representations. From this inequality, we obtained that each element of Zp can be represented as the sum of a Lehmer number and a primitive root for p > 2.5×1014. Moreover, using the algorithm we provided, we examined all the cases when p < 106 by computer. We also analyzed the time complexity of the algorithm and illustrated that it is extremely difficult to verify all the cases up to the bound 2.5×1014, and conjectured that any given element n ∈ Zp can be represented as the sum of a Lehmer number and a primitive root in Zp for all primes p except 2, 3, 5, 7, 11, 19, 31. [ABSTRACT FROM AUTHOR]

Cellular automata are mathematical models that represent systems with complex behavior through simple interactions between their individual elements. These models can be used to study unconventional computational systems and complexity. One notable aspect of cellular automata is their ability to create structures known as gliders, which move in a regular pattern to represent the manipulation of information. This paper introduces the modification of mean-field theory applied to cellular automata, using random perturbations based on the system's evolution rule. The original aspect of this approach is that the perturbation factor is tailored to the nature of the rule, altering the behavior of the mean-field polynomials. By combining the properties of both the original and perturbed polynomials, it is possible to detect when a cellular automaton is more likely to generate gliders without having to run evolutions of the system. This methodology is a useful approach to finding more examples of cellular automata that exhibit complex behavior. We start by examining elementary cellular automata, then move on to examples of automata that can generate gliders with more states. To illustrate the results of this methodology, we provide evolution examples of the detected automata. [ABSTRACT FROM AUTHOR]

Path planning is crucial in the scheduling and motion planning of multiple robots. However, solving multi-robot path-planning problems efficiently and quickly is challenging due to their high complexity and long computational time, especially when dealing with many robots. This paper presents a unified mathematical model and algorithm for the path planning of multiple robots moving from one formation to another in an area with obstacles. The problem was initially simplified by constructing a cost matrix, and then the route planning was achieved by integrating an elite enhanced multi-population genetic algorithm and an ant colony algorithm. The performance of the proposed planning method was verified through numerical simulations in various scenarios. The findings indicate that this method exhibits high computational efficiency and yields a minimal overall path distance when addressing the path-planning problem of a multi-robot formation reconstruction. As a result, it holds promising potential for the path-planning problem of a multi-robot formation reconstruction. [ABSTRACT FROM AUTHOR]

Undetected infections fuel the dissemination of many infectious agents. However, identification of unobserved infectious individuals remains challenging due to limited observations of infections and imperfect knowledge of key transmission parameters. Here, we use an ensemble Bayesian inference method to infer unobserved infections using partial observations. The ensemble inference method can represent uncertainty in model parameters and update model states using all ensemble members collectively. We perform extensive experiments in both model-generated and real-world networks in which individuals have differential but unknown transmission rates. The ensemble method outperforms several alternative approaches for a variety of network structures and observation rates, despite that the model is mis-specified. Additionally, the computational complexity of this algorithm scales almost linearly with the number of nodes in the network and the number of observations, respectively, exhibiting the potential to apply to large-scale networks. The inference method may support decision-making under uncertainty and be adapted for use for other dynamical models in networks. Author summary: Mathematical models in networks can be used to infer unobserved infections and support decision-making in outbreak control and management. However, a major challenge in the operational use of these models is model misspecification–whether models can reliably represent the real-world disease transmission process. As we can only observe part of the transmission process, mathematical models are inherently misspecified due to the uncertainty in the model structure and parameters. A reliable modeling method, therefore, should be robust to such uncertainty and imperfect knowledge of the transmission dynamics to support real-time decision-making. In this study, we used an ensemble inference method to infer unobserved infections using partial observations. We considered the condition where individuals have differential but unknown transmission rates as an example of model uncertainty mirroring the situation encountered in real-world settings. We found the ensemble inference can robustly infer unobserved infections using partial observations with uncertainty in model parameters, although the distribution of parameters is mis-specified. The ensemble inference algorithm presents a general framework for inference of spreading dynamics in networks and may contribute to the toolbox supporting operational epidemic control in the face of model uncertainty and limited observation. [ABSTRACT FROM AUTHOR]

In a hybrid microgrid with AC and DC subgrids, the interlinking converter (IC) is the key element connecting the two subgrids. The performance of the interlinking converter is adversely affected by the d- and q-axis impedance interaction between the inner control loops. This interaction is highly undesirable since it adversely affects both the dynamic and the steady-state performance of the IC. Based on this, a novel feedback-based decoupling strategy is developed to overcome the cross-coupling effect in the mathematical model of the interlinking converter. This is a novel concept since the feed-forward compensation techniques are utilized to address the cross-coupling effect in prior related works, which has an inherent disadvantage of additional disturbance due to the addition of the compensating terms. In this study, a complete decoupling of the d and q axes was achieved, and the first-order transfer functions were obtained for the control loops using systematic block-reduction algebra and direct synthesis approaches. With this model, computational complexities are reduced and the inner control loops are free from impedance interaction effects, thereby achieving enhanced transient stability. Perfect decoupling of the voltage vectors is achieved by the matrix diagonalization method. Furthermore, the novelty of the proposed control is that the decoupled model is integrated with a normalization-based coordinate control strategy for effective bidirectional power transfer via the interlinking converter. Additionally, the proposed controller's validity was tested for its performance under different transients in the MATLAB Simulink platform. The simulation results validated the proposed control strategy by showing that a faster response is ensured. A high-quality reference signal is generated due to the effective decoupling achieved. This observation was also validated by comparing the T.H.D. levels of a decoupled model's reference power signal to one without a decoupling strategy. [ABSTRACT FROM AUTHOR]

Fast and accurate power-flow methods are of great importance, especially in near real-time optimal operation of power systems. This importance will be even more highlighted in the presence of more repetitions of power-flow calculations, which cause more computational complexities in optimization problems. As a solution, in this paper, a novel fast and accurate approach of linear power-flow formulation is proposed. Principles of the proposed approach are based on dividing power-flow calculations into base and variable parts. To this aim, at first, system modeling of base and variable parts are presented. For the base-part modeling, utilizing a nonlinear power-flow, an accurate base power-flow (BPF) is extracted. Afterwards, by linearizing the power system around the BPF, variable-part model which is the result of a linear fitting process, is obtained. Then, it is shown that the variable-part of the operating point is always a function of the obtained base-part and variable-part models. In this paper, by focusing on the stochastic application of the proposed approach, different uncertainties in a distribution system are considered. Finally, numerical results carried out in the Matlab environment, for a IEEE 34-bus standard distribution system and then a 1486-bus case study, verify the performance of the proposed approach. [ABSTRACT FROM AUTHOR]

This paper proposes a hybrid successive over-relaxation iterative method for the numerical solution of a nonlinear diffusion in a one-dimensional porous medium. The considered mathematical model is discretized using a computational complexity reduction scheme called half-sweep finite differences. The local truncation error and the analysis of the stability of the scheme are discussed. The proposed iterative method, which uses explicit group technique and modified successive over-relaxation, is formulated systematically. This method improves the efficiency of obtaining the solution in terms of total iterations and program elapsed time. The accuracy of the proposed method, which is measured using the magnitude of absolute errors, is promising. Numerical convergence of tests the proposed method are also provided. Some numerical experiments are delivered using initial-boundary value problems to show the superiority of the proposed method against some existing numerical methods. [ABSTRACT FROM AUTHOR]

The notion of multi-granularity has been introduced into various mathematical models in granular computing. For example, neighborhood rough sets can derive a good multi-granularity structure by gradually changing the size of neighborhood radius. Attribute reduction is an important topic in neighborhood rough sets. However, in the case of multi-granularity, the challenge of high computational complexity and difficulty in synthesizing multi-granularity information when performing reduction algorithms always exists. To address such limitations, an accelerated algorithm for multi-granularity reduction is designed. Firstly, we construct a multi-granularity reduction structure with multiple different neighborhood radii to reduce the elapsed time of computing reducts. In this way, the consumed time of calculating the distance is similar to the one of single granularity reduction, and the elapsed time of computing multi-granularity reducts can be reduced. Secondly, multiple granularity information is integrated in each attribute evaluation. Finally, we evaluated the proposed method from multiple perspectives on 12 UCI datasets. Compared with other multi-granularity reduction algorithms, the proposed method not only generates reducts with relatively high quality, but also improves the time efficiency of multi-granularity reduction algorithm. [ABSTRACT FROM AUTHOR]

In this brief, a q-Rényi kernel functioned Kalman filter (qRKFKF) is proposed based on the q-Rényi kernel function which is to provide better flexibility and performance in non-Gaussian environment. The concrete realization of the proposed qRKFKF are created and analyzed in detail, and its performance is presented and discussed. Three examples are carried out to verify the performance of the proposed qRKFKF for land vehicle navigation via numerical simulations: large outliers in non-Gaussian noise, alpha-stable noise and diverse noise distributions that combines Gaussian and Laplace noises. Compared with Kalman filter (KF), Maximum Correntropy Kalman Filter (MCKF) and minimum error entropy KF (MEE-KF), the qRKFKF is superior to others for combating non-Gaussian noises. [ABSTRACT FROM AUTHOR]

The emerging concept of drone swarms creates new opportunities with major societal implications. However, future drone swarm applications and services pose new communications and sensing challenges, particularly for collaborative tasks. To address these challenges, in this paper, we integrate sensor arrays and communication to propose a mathematical model to route a collection of autonomous unmanned aerial systems (AUAS), a so-called drone swarm or AUAS swarm, without having a base station of communication but communicating with each other using multiple spatio-temporal data. The theories of structured matrices, concepts in multi-beam beamforming, and sensor arrays are utilized to propose a swarm routing algorithm. We address the routing algorithm's computational and arithmetic complexities, precision, and reliability. We measure bit-error-rate (BER) based on the number of elements in sensor arrays and beamformed output of the members of the swarm to authenticate and secure the routing for the decentralized AUAS networking. The proposed model has the potential to enable future drone swarm applications and services. Finally, we discuss future work on obtaining a machine-learning-based low-cost drone swarm routing algorithm. [ABSTRACT FROM AUTHOR]

The paper presents several novel residual recurrent neural network (RNN) models for digital predistortion of radio-frequency power amplifiers. Then, unstructured and structured neural network (NN) pruning algorithms are proposed to reduce the per-sample computational complexity and the required memory, without compromising their modeling performance. The mathematical equations of the complexity and the memory are derived to analyze the hardware cost and design low cost models. An experimental platform is developed to measure the modeling performance in terms of adjacent channel leakage ratio (ACLR), normalized mean square error, error vector magnitude (EVM) and bit error rate. The platform uses an envelope tracking PA excited by 80 MHz IEEE 802.11ac signals. Compared with the state-of-the-art RNN model in (Sun et al., 2019), the proposed models reduce the per-sample complexity and required memory by $94\hbox{--}99$ %, they also improve the ACLR and EVM by at least 3 dB and 1 dB at 0.45 dB and 3.15 dB gain compression, respectively. Furthermore, an observation path with time alignment is used to remove the transmit latency in the state-of-the-art approach. At 3.15 dB gain compression, the proposed models outperform the state-of-the-art feedforward and convolutional NN models by at least 1.3 dB in EVM, outperform the general memory polynomial model by at least 3.3 dB in EVM. The above evidences indicate that the proposed RNN models can be implemented with relatively low hardware cost and achieve the best EVM in high power efficiency scenario. [ABSTRACT FROM AUTHOR]

In this paper, we focus on decoding nonbinary low-density parity-check (LDPC) codes in Galois fields of characteristic two via the proximal alternating direction method of multipliers (proximal-ADMM). By exploiting Flanagan/Constant-Weighting embedding techniques and the decomposition technique based on three-variables parity-check equations, two efficient proximal-ADMM decoders for nonbinary LDPC codes are proposed. We show that both of them are theoretically guaranteed convergent to some stationary point of the decoding model and either of their computational complexities in each proximal-ADMM iteration scales linearly with LDPC code’s length and the size of the considered Galois field. Moreover, the decoder based on the Constant-Weight embedding technique satisfies the favorable property of codeword symmetry. Simulation results demonstrate their effectiveness in comparison with state-of-the-art LDPC decoders. [ABSTRACT FROM AUTHOR]

Since the observed angle of a phase-locked loop (PLL) is relatively accurate even under distorted grid conditions, the mathematical model of the voltage errors caused by the switching modulation and the dead-time effect are derived as a function of the grid voltage angle in this paper. Based on the model analysis, an adaptive compensation algorithm is proposed to suppress the grid-side current harmonics in three-phase converters. The proposed algorithm fits the unmeasurable voltage errors by a truncated Fourier series expansion, and then takes it as an equivalent disturbance in the current control loop to achieve harmonic compensation. By the feed-forward compensation, the design and tuning of the controller parameters are simplified and separated from the dynamic performance. In addition, the controller can adapt to the grid frequency variation by updating the grid voltage angle with the PLL block. To reduce the computational burden, a simplified version of the proposed method is also presented. Simulation and experiment results show that the proposed methods can suppress the current harmonics and achieve better performance in terms of total harmonic distortion, strong robustness and insensitivity to the grid frequency variations, compared with the traditional PI control or repetitive control strategy. [Display omitted] • A PI controller is designed to ensure satisfactory dynamic performance. • An adaptive method is employed to compensate the voltage errors caused by the switching modulation and the deadtime effect so as to suppress the grid current harmonics. • A simplified adaptive strategy is also presented to reduce the computational burden and the complexity to half of the original method. • The adaptive algorithm is less model-dependent and built based on the grid voltage angle with a PLL to achieve frequency adaption. [ABSTRACT FROM AUTHOR]

In this paper we introduce the electromechanical mathematical model of the human heart. After deriving it from physical first principles, we discuss its mathematical properties and the way numerical methods can be set up to obtain numerical approximations of the (otherwise unachievable) mathematical solutions. The major challenges that we need to face—e.g., possible lack of initial and boundary data, the trade off between increasing the accuracy of the numerical model and its computational complexity—are addressed. Numerical tests here presented have a twofold aim: to show that numerical solutions match the expected theoretical rate of convergence, and that our model can provide a preliminary valuable tool to face problems of clinical relevance. [ABSTRACT FROM AUTHOR]

The estimating returns to scale (RTS) and identifying the area in which the type of returns to the scale of a single decision maker unit (DMU) remains sustainable helps managers to have more accurate predictions about the size variations of a DMU. Contrary to theoretical studies and attitudinal surveys, the RTS-based econometric estimates of the panel data are derived from the time changes observed in inputs and outputs. Therefore the description of returns-to-scale based on the panel data is closer to those that are related to changes in demand and changes in the policy of managers during the sample period. it’s clear that the use of the panel data, in addition to estimating returns to scale closer to the view of the managers, leads to a significant increase in the number of inputs and outputs for each DMU. Since we know that the DEA models have computational complexity for the great practical issues, use particularly when there are large numbers of outputs and inputs reducing the number of models will greatly help to solve these issues. In most articles, the returns-to-scale estimates for decision-making units (DMU) are performed with at least two LP models. Furthermore have problems in some cases and may not be able to investigate all DMUs. In this paper, a method has been proposed which determines returns-to-scale and identifies boundary units by solving only one model. In fact, unlike some articles which explore the boundary DMUs, the assessment area in this paper is all the DMUs observed in PPS (Production Possible Set). Therefore, based on this approach, identifying boundary units and estimating their returns-to-scale will be possible by solving only one LP model. Further, according to the proposed dual model, a different perspective has been proposed to identify and evaluate boundary units and to estimate the returns-to-scale by solving a single LP model. Additionally and according to numerous observations, the dual model is able to estimate the returns-to-scale of the image point of the inefficient units in the BCC model in the input orientation. The correctness of all content has been shown theoretically as well as intuitively, with due substantiation. [ABSTRACT FROM AUTHOR]

It is an essential technique for the moving user nodes (UNs) with clock offset and clock skew to resolve the joint localization and synchronization (JLAS) problem. Existing iterative maximum likelihood methods using sequential one-way time-of-arrival (TOA) measurements from the anchor nodes’ (AN) broadcast signals require a good initial guess and have a computational complexity that grows with the number of iterations, given the size of the problem. In this paper, we propose a new closed-form JLAS approach, namely CFJLAS, which achieves the asymptotically optimal solution in one shot without initialization when the noise is small, and has a low computational complexity. After squaring and differencing the sequential TOA measurement equations, we devise two intermediate variables to reparameterize the non-linear problem, and convert it to a simpler one of solving two simultaneous quadratic equations. We then solve the equations analytically to obtain a raw closed-form JLAS estimation. Finally, we apply a weighted least squares (WLS) step to optimize the estimation. We derive the Cramér-Rao lower bound (CRLB), analyze the estimation error, and show that the estimation accuracy of the CFJLAS reaches the CRLB under the small noise condition. The complexity of the new CFJLAS is only determined by the size of the problem, unlike the conventional iterative method, whose complexity is additionally multiplied by the number of iterations. Simulations in a 2D scene verify that the estimation accuracies of the new CFJLAS method all reach the CRLB under the small noise condition. Compared with the conventional iterative method, the proposed new CFJLAS method does not require initialization, obtains the optimal solution under the small noise condition, and has a low computational complexity. [ABSTRACT FROM AUTHOR]

Wide-area backup protection (WABP) refers to the identification of the faulted line amongst candidate lines by using sparse PMU measurements. This letter proposes a technique for reducing the computational complexity of WABP methods that employ the superimposed-circuit concept. A proposition is presented and proved to justify that the system of equations pertaining to every candidate line can be directly obtained from the bus impedance matrix of the pre-fault power system. This is in contrast with existing WABP methods requiring the establishment of as many distinct bus impedance matrices as the number of candidate lines in the power system. The applicability and effectiveness of the proposed technique are verified by conducting more than 20,000 simulations on the IEEE 39-bus test system. [ABSTRACT FROM AUTHOR]

Massive multiple-input multiple-output (mMIMO) is a promising technique to realize the ever-increasing demand for high-speed data, quality of service (QoS), and energy efficiency for 5G and beyond wireless systems. However, the increased number of users in mMIMO systems significantly affects performance of the existing approximate matrix inversion based and matrix inversion less iterative symbol detection techniques. Conventional detection algorithms cannot learn the inter-relations of input-output parameters based on available data without having specific mathematical models of communication scenarios. Moreover, existing deep learning (DL) based symbol detection models lack in-network compression, resulting in large training time and high computational load while expected to be deployed in a low latency communication system. In this article, a sparse refinement architecture is proposed for symbol detection in uplink mMIMO. The proposed DL architecture requires less trainable parameters as compared to a conventional fully connected detection network and refines the estimated symbol vector in each layer. Convergence of the proposed symbol detection technique is analytically justified. An expression for the approximate upper bound on the BER is derived which is supported by simulations. The obtained results prove viability of the proposed symbol detection model as compared to the several existing state-of-art uplink mMIMO detection techniques, in terms of superior the error performance and low computational complexity. [ABSTRACT FROM AUTHOR]

This article discusses the properties of the practical application results of the Coulomb and the “tree-cotree” gauge conditions for problems based on massive finite element 3-D-meshes (up to 12 million tetrahedrons) and with the ${A}$ – ${V}$ formulation of the magnetic potential. The influence of the sort of gauging of the magnetic vector potential on the accuracy of the calculated solution of systems of linear algebraic equations (SLAEs) is shown by the example of magnetostatics and quasi-static (frequency domain) benchmark problems. The study was carried out for the cases of solving problems by iterative methods of the Krylov subspace and by direct methods. Iterative methods have shown the complexity of achieving the required solution accuracy with an increase in the number of finite elements and deterioration of the properties of the SLAE. The analysis of the dependence of the iterative process convergence and the required solution accuracy on the number of elements in the mesh and the type of gauging applied is accomplished. For direct methods for solving SLAEs, an a posteriori estimate of the dependence of the value of the relative forward error on the presence and type of the gauge condition is performed. The possibility and efficiency of using block low-rank (BLR) factorization for solving SLAEs in the presence and absence of gauge conditions are considered. The conditions for using the gauging of the magnetic vector potential are shown, which are suitable for simplifying the process of preparing and solving numerical problems and increasing the accuracy of the calculated values of the magnetic vector potential in the frequency domain. [ABSTRACT FROM AUTHOR]

This article presents an optimization-based control framework for the autonomous forced landing of a fixed-wing unmanned aircraft (UA). A two-level model-predictive control (MPC) scheme is proposed to realize this framework, where an economic model-predictive control (EMPC) in a long piecewise constant fashion is proposed at the high level, while a short fixed-horizon linear time-varying MPC at the low level responds to fast dynamics of UA and tracks the optimal path provided by the high-level controller, alleviating computational burden compared to the high-frequency single-layer MPC scheme. Compared with a single EMPC setup with high sampling frequency, this hierarchical EMPC controller can significantly reduce the computational complexity and make it feasible to be implemented in real time. In addition, it also responds to disturbances (e.g., wind) and aircraft fast dynamics in a timely manner. The recursive feasibility and stability of the high- and low-level MPC schemes are established. The performance of the proposed EMPC forced landing function is illustrated by simulation case studies on both Aerosonde and Skywalker X8, compared favorably with competing schemes. [ABSTRACT FROM AUTHOR]

Three mathematical models have been used to predict the dehydration kinetics of grape pomace. To the aim, three different temperatures have been set to determine the different desorption kinetics. All the dehydration kinetic data have been fitted to verify the predictive ability of the proposed models. The fitting goodness were assessed by using four coefficients: E ‾ % , R M S E , χ 2 , and R 2. Results show that all the proposed models can adequately fit the experimental data. In particular, the Dual-Stage Type B model is the best one, whereas the Fick model is the worst. The soundness of the mathematical approach adopted was tested by assessing the dependence of the model's parameters on the testing temperature: only some parameters followed the expected trend. The computational complexity referred to each model was considered evaluating the suitability of the proposed models to describe the desorption kinetics. To sum up, the Dual-Stage Type B model is the most complex, whereas the simplest one is the Dual-Stage Type A model. Considering both suitability and complexity, the Dual-Stage Type A is the best model to predict the dehydration kinetic of grape pomace. • 3 models have been used to predict grape pomace's dehydration kinetic. • The best but most complex model is the Dual-Stage Type B model. • The Dual-Stage Type A combines good predictive capacity with simplicity. [ABSTRACT FROM AUTHOR]

In the 3-D density inversion calculation of gravity data, the entire subsurface space is discretized into rectangular prisms, and the density value of each prism is calculated. However, the method of dividing the entire space often results in invalid calculations. In this study, we proposed a highly efficient density inversion method using a locally adaptive unstructured mesh. In this method, the inversion scope is reduced by using the feature that the zero value of the tilt angle method corresponds to the edge of the field source. In addition, the local inversion area is divided by unstructured meshes, which can better represent irregular geological bodies and undulating terrain. In the proposed method, the size of the grid cells is changed according to the value of the tilt angle to reduce the amount of mesh, which reduces the computational complexity and improves the computational efficiency. In addition, by introducing a volume weighting function, the sensitivity of grid cells of different sizes can be balanced. Through synthetic modeling experiments, we verified that the locally adaptive unstructured mesh method can improve the efficiency and accuracy of inversion, flexibly deal with undulating terrain, and obtain the distribution features of irregular bodies. We applied this method to gravimetric data of the North Qinling region of the Shaanxi province, which clearly shows the spatial distribution information of five high-density geological bodies, and the depth range of ore bodies formed is from 240 to 1481 m according to our inversion results. [ABSTRACT FROM AUTHOR]

Let G = (V (G),E(G)) be a finite simple undirected graph with vertex set V (G), edge set E(G) and vertex subset S ⊑ V (G). S is termed open-dominating if every vertex of G has at least one neighbor in S, and open-independent, open-locating-dominating (an OLDoind-set for short) if no two vertices in G have the same set of neighbors in S, and each vertex in S is open-dominated exactly once by S. The problem of deciding whether or not G has an OLDoind-set has important applications that have been reported elsewhere. As the problem is known to be NP-complete, it appears to be notoriously difficult as we show that its complexity remains the same even for just planar bipartite graphs of maximum degree five and girth six, and also for planar subcubic graphs of girth nine. Also, we present characterizations of both P4-tidy graphs and the complementary prisms of cographs that have an OLDoind-set. [ABSTRACT FROM AUTHOR]

Copyright of Ingeniería (0121-750X) is the property of Ingenieria 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 automated planning, the need for explanations arises when there is a mismatch between a proposed plan and the user's expectation. We frame Explainable AI Planning as an iterative plan exploration process, in which the user asks a succession of contrastive questions that lead to the generation and solution of hypothetical planning problems that are restrictions of the original problem. The object of the exploration is for the user to understand the constraints that govern the original plan and, ultimately, to arrive at a satisfactory plan. We present the results of a user study that demonstrates that when users ask questions about plans, those questions are usually contrastive, i.e. "why A rather than B?". We use the data from this study to construct a taxonomy of user questions that often arise during plan exploration. Our approach to iterative plan exploration is a process of successive model restriction. Each contrastive user question imposes a set of constraints on the planning problem, leading to the construction of a new hypothetical planning problem as a restriction of the original. Solving this restricted problem results in a plan that can be compared with the original plan, admitting a contrastive explanation. We formally define model-based compilations in PDDL2.1 for each type of constraint derived from a contrastive user question in the taxonomy, and empirically evaluate the compilations in terms of computational complexity. The compilations were implemented as part of an explanation framework supporting iterative model restriction. We demonstrate its benefits in a second user study. [ABSTRACT FROM AUTHOR]

XOR arbiter PUF (XOR APUF), where the outputs of multiple arbiter PUF (APUFs) are XOR-ed, has proven to be more robust to machine learning-based modeling attacks. The reported successful modeling attacks for XOR APUF either employ auxiliary side-channel or reliability information, or require enormous computational effort. This robustness is primarily due to the difficulty in learning the unknown internal delay parameter terms in the mathematical model of a XOR APUF, and the robustness increases as the number of APUFs being XOR-ed increases. In this article, we employ a novel machine learning-based modeling technique called efficient CANDECOMP/PARAFAC-tensor regression network (CP-TRN), a variant of CP-decomposition-based tensor regression network, to reduce the computational resource requirement of model building attacks on XOR APUF. We theoretically prove the reduction in computational complexity, as well as give supporting experimental results. In addition, our proposed technique does not require any auxiliary information, and is robust to noisy training data. The proposed technique allowed us to successfully model 64-bit 8-XOR APUF and 128-bit 7-XOR APUF on a single desktop workstation, with high prediction accuracy. Further, we extend the proposed modeling attack technique to XOR APUF variants, e.g., lightweight secure PUF (LSPUF), which rely on input challenge transformation. The modeling accuracy results obtained by us for the LSPUF are comparable with those obtained by applying other state-of-the-art techniques, while requiring less training data. [ABSTRACT FROM AUTHOR]

Within the scope of this article, the problem of the formalization of physical processes in adaptive training complexes is considered on the example of virtual objects burning. Despite a fairly complete study of this process, the existing mathematical models are not adapted for the application in training complexes, which leads to a significant increase in costs and lower productivity due to the complexity of the calculations. Therefore, an adapted mathematical model is proposed that allows us to formalize the structure of virtual objects of burning, their basic properties and the processes of changing states, starting from the flame development of an object and ending with their complete destruction or extinguishment. The article proposes the use of threshold value diagrams and rules for changing the states of virtual reality objects to solve the problem of the formalization of burning processes. This tool is quite multi-purpose, which allows you to describe various physical processes, such as smoke, flooding, the spread of toxic gases, etc. The area of the proposed formalization approach includes the design and implementation of physical processes in simulators and multimedia complexes using virtual and augmented reality. Thus, the presented scientific research can be used to formalize the physical processes in adaptive training complexes for professional ergatic systems. [ABSTRACT FROM AUTHOR]

Successful progression from bench to bedside for regenerative medicine products is challenging and requires a multidisciplinary approach. What has not yet been fully recognised is the potential for quantitative data analysis and mathematical modelling approaches to support this process. In this review, we highlight the wealth of opportunities for embedding mathematical and computational approaches within all stages of the regenerative medicine pipeline. We explore how exploiting quantitative mathematical and computational approaches, alongside state-of-the-art regenerative medicine research, can lead to therapies that potentially can be more rapidly translated into the clinic. [ABSTRACT FROM AUTHOR]

Hybrid and intermittent characteristics of the distributed energy resources (DERs) bring great challenges to the security control and economic dispatch (ED) of the microgrids. To bypass these hurdles, this article proposes a multiagent system-based integrated design of security control and ED to guarantee the effective and economical operation of the interconnected microgrids. First, a hierarchical control scheme is constructed by two-level unit agents, in which the switching control and dynamic regulation are fully implemented with the corresponding hybrid behaviors based on the differential hybrid Petri-net (DHPN) model. Based on the DHPN model, a novel dynamic ED integrated with security control is proposed to overcome the issues that cannot be solved in conventional models. Furthermore, to reduce the computational complexity and unified the mathematical model of the DERs, the inverter-based power control strategy is converted to a predictive control model which can be decomposed into several subsystems. In the optimization process, all the subsystems are implemented in a fully distributed, communication free, and rolling optimization manner based on the distributed model predictive control (DMPC). The validity of the proposed design is demonstrated according to the simulation results in case studies. [ABSTRACT FROM AUTHOR]

The recommender systems are used to mainly suggest recommendations to the online users by utilizing the user preferences recorded during the item purchase. No matter how, the performance of the recommendation quality seems to be inevitable and far satisfactory. In this paper, a new approach based on the mathematical model, Formal Concept Analysis (FCA) is used to improve the rating prediction of the unknown users which can certainly overcome the issues of the existing approaches like data sparsity, high dimensionality of data, performance of the recommendation generated for top n recommendation. The FCA method is applied using Boolean Matrix Factorization (ie. optimal formal concepts) in predicting the rating of the unknown users in the available user-item interaction matrix which proves to be more efficient in tackling the problem of computational complexity managing the high dimensionality of data. The proposed method is applied using item-based collaborative filtering technique and the experiment is conducted on the Movielens dataset which shows the satisfactory results. The experiments results are evaluated using the related error metrics and performance metrics. The experimental results are also compared with existing item-based Collaborative Filtering techniques which demonstrate that the performance of recommendation quality gradually improved with state-of-the-art existing techniques. [ABSTRACT FROM AUTHOR]

We bound the time it takes for a group of birds to stabilize in a standard flocking model. Each bird averages its velocity with its neighbors lying within a fixed radius. We resolve the worst-case complexity of this natural algorithm by providing asymptotically tight bounds on the time to equilibrium. We reduce the problem to two distinct questions in computational geometry and circuit complexity. [ABSTRACT FROM AUTHOR]

When defining computations over syntax as data, one often runs into tedious issues concerning α-equivalence and semantically correct manipulations of binding constructs. Here we study a semantic framework in which these issues can be dealt with automatically by the programming language. We take the user-friendly "nominal" approach in which bound objects are named. In particular, we develop a version of Scott domains within nominal sets and define two programming languages whose denotational semantics are based on those domains. The first language, λv-PCF, is an extension of Plotkin's PCF with names that can be swapped, tested for equality and locally scoped; although simple, it already exposes most of the semantic subtleties of our approach. The second language, PNA, extends the first with name abstraction and concretion so that it can be used for metaprogramming over syntax with binders. For both languages, we prove a full abstraction result for nominal Scott domains analogous to Plotkin's classic result about PCF and conventional Scott domains: two program phrases have the same observable operational behaviour in all contexts if and only if they denote equal elements of the nominal Scott domain model. This is the first full abstraction result we know of for languages combining higher-order functions with some form of locally scoped names which uses a domain theory based on ordinary extensional functions, rather than using the more intensional approach of game semantics. To obtain full abstraction, we need to add two functionals, one for existential quantification over names and one for "definite description" over names. Only adding one of them is not enough, as we give counterexamples to full abstraction in both cases. [ABSTRACT FROM AUTHOR]

In this paper, a model predictive direct power control (MP-DPC) with power compensation and circulating current reduction is proposed for modular multilevel converter under unbalanced grid conditions. The main objectives of this paper are to achieve the circulating currents reduction and the power ripples elimination under unbalanced grid-side voltage conditions. In order to realize the aforementioned objectives, a triple-stage MP-DPC method based on a decoupled mathematical model of circulating current and DC-link current components is presented, which results in the elimination of weighting factors. Meanwhile, a power compensation term is embedded in the proposed design so as to eliminate the power ripples. In this sense, the power compensation terms are expressed by grid voltages and their quadrature signals without the complex positive/negative sequences extraction of grid voltage/currents and phase-locked loop. The proposed methodology can not only relieve the effect of circulating currents but also eliminate the active and reactive power ripples while remaining computationally feasible under unbalanced grid conditions. Additionally, a reduced switching frequency approach is introduced to decrease the power loss. Finally, the effectiveness of the proposed MP-DPC method is validated by both simulation and experimental results. • A triple-stage FCS-MPC method is proposed to regulate multiple control objectives of MMC, which results in the elimination of weighting factors. • To enhance the grid-side power quality, the proposed strategy takes power compensation scheme into consideration under unbalanced grid-side conditions. • Compared with the conventional MP-DPC method, the circulating current and switching frequency are restrained in this design while not punishing the computational complexity. [ABSTRACT FROM AUTHOR]

A method to find the minimized state machine cover of live and safe Petri nets (PNs) is proposed in this paper. It is required that a cover be obtained in some implementation methods of PN-based control algorithms and other applications such as data mining. Most of the known methods of its computation have at least exponential time and space complexity; this is true not only for the methods which guarantee a minimal cover is obtained but also for some methods of finding approximate solutions. The proposed algorithm is an approximation algorithm and has polynomial computational complexity. The experimental verification shows a very high efficiency of the presented technique. The proposed method is especially valuable in the case of large systems where a solution is obtained hundreds of times quicker than by other methods. [ABSTRACT FROM AUTHOR]

Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this article, we focus on the problem of sampling random walks efficiently in a distributed network and its applications. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain random walk samples. All previous algorithms that compute a random walk sample of length ℓ as a subroutine always do so naively, that is, in O(ℓ) rounds. The main contribution of this article is a fast distributed algorithm for performing random walks. We present a sublinear time distributed algorithm for performing random walks whose time complexity is sublinear in the length of the walk. Our algorithm performs a random walk of length ℓ in Õ(√lD) rounds (Õ hides polylog n factors where n is the number of nodes in the network) with high probability on an undirected network, where D is the diameter of the network. For small diameter graphs, this is a significant improvement over the naive O(ℓ ) bound. Furthermore, our algorithm is optimal within a poly-logarithmic factor as there exists a matching lower bound [Nanongkai et al. 2011]. We further extend our algorithms to efficiently perform k independent random walks in Õ(√ kℓ D + k) rounds. We also show that our algorithm can be applied to speedup the more general Metropolis-Hastings sampling. Our random-walk algorithms can be used to speed up distributed algorithms in applications that use random walks as a subroutine. We present two main applications. First, we give a fast distributed algo-rithm for computing a random spanning tree (RST) in an arbitrary (undirected unweighted) network which runs in Õ(√mD) rounds with high probability (m is the number of edges). Our second application is a fast decentralized algorithm for estimating mixing time and related parameters of the underlying network. Our algorithm is fully decentralized and can serve as a building block in the design of topologically-aware networks. [ABSTRACT FROM AUTHOR]

Resource allocation and transceivers in wireless networks are usually designed by solving optimization problems subject to specific constraints, which can be formulated as variable or functional optimization. If the objective and constraint functions of a variable optimization problem can be derived, standard numerical algorithms can be applied for finding the optimal solution, which however incurs high computational cost when the dimension of the variable is high. To reduce the on-line computational complexity, learning the optimal solution as a function of the environment's status by deep neural networks (DNNs) is an effective approach. DNNs can be trained under the supervision of optimal solutions, which however, is not applicable to the scenarios without models or for functional optimization where the optimal solutions are hard to obtain. If the objective and constraint functions are unavailable, reinforcement learning can be applied to find the solution of a functional optimization problem, which is however not tailored to optimization problems in wireless networks. In this article, we introduce unsupervised and reinforced-unsupervised learning frameworks for solving both variable and functional optimization problems without the supervision of the optimal solutions. When the mathematical model of the environment is completely known and the distribution of the environment's status is known or unknown, we can invoke an unsupervised learning algorithm. When the mathematical model of the environment is incomplete, we introduce reinforced- unsupervised learning algorithms that learn the model by interacting with the environment. Our simulation results confirm the applicability of these learning frameworks by taking a user association problem as an example. [ABSTRACT FROM AUTHOR]

Aiming at the dynamic and nonlinear characteristics of batch process, a multiway dynamic nonlinear global neighborhood preserving embedding algorithm is proposed. For the nonlinear batch process monitoring, kernel mapping is widely used to eliminate nonlinearity by projecting the data into high-dimensional space, but the nonlinear relationships between batch process variables are limited by many physical constraints, and the infinite-order mapping is inefficient and redundant. Compared with the basic kernel mapping method which provides an infinite-order nonlinear mapping, the proposed method considers the dynamic and nonlinear characteristics with many physical constraints and preserves the global and local structures concurrently. First, the time-lagged window is used to remove the auto-correlation in time series of process variables. Second, a nonlinear method named constructive polynomial mapping is used to avoid unnecessary redundancy and reduce computational complexity. Third, the global neighborhood preserving embedding method is used to extract structures fully after the dynamic and nonlinear characteristics are processed. Finally, the effects of the proposed algorithm are demonstrated by a mathematical model and the penicillin fermentation process. [ABSTRACT FROM AUTHOR]

Recently, a robust least squares support vector machine (R-LSSVM) was proposed, but its computational complexity is very high compared with the traditional least squares support vector machine (LSSVM). To reduce R-LSSVM's computational complexity, an improved version, i.e., extended LSSVM (E-LSSVM), is developed in this paper. E-LSSVM and R-LSSVM are equivalent in terms of the generalization performance, but the former needs lower computational complexity than the latter. It is proved that the traditional LSSVM is a special case of E-LSSVM, and based on this fact, we know that the bias in the traditional LSSVM owns manifest physical meaning, i.e., the mean of the modeling error. To solve the mathematical model of E-LSSVM, two algorithms, DE-LSSVM (dual E-LSSVM) and PE-LSSVM (primal E-LSSVM), are proposed from dual and primal spaces, respectively. Even competing against the traditional LSSVM, DE-LSSVM takes the edge in term of the training time. In addition, the sparse problem and cross validation of DE-LSSVM are discussed as well. To verify the effectiveness and soundness of the proposed DE-LSSVM and PE-LSSVM, experiments on regression and classification problems are investigated. To be more important, DE-LSSM and PE-LSSVM are successfully applied to the fault diagnosis of aircraft engine, showing that they are eligible for potential techniques of the fault diagnosis of aircraft engine. [ABSTRACT FROM AUTHOR]

It is a widespread financial practice in procurement management for a supplier aiming to attract customers to offer trade credits when customers make inquiries about the sold products. In this paper, we examine the joint replenishment problem considering trade credits (JRP-TC) under the power-of-two (PoT) policy. We formulate a mathematical model and conduct an analysis that reveals insights into the properties of the optimal objective function. From there, we propose an effective search algorithm that obtains the global optimal solution for the JRP-TC under the PoT policy. Our complexity analysis shows that the JRP-TC and the conventional joint replenishment problem under the PoT policy are pseudo-polynomial time solvable. [ABSTRACT FROM AUTHOR]

In network-centric warfare, the interconnections among various combat resources enable an advanced operational pattern of cooperative engagement. The operational effectiveness and outcome strongly depends on the reasonable utilization of available sensors and weapons. In this paper, a mathematical model for the coallocation of sensors and weapons is built, taking into account the interdependencies between weapons and sensors, the resource constraints, the capability constraints, as well as the strategy constraints. A marginal-return-based constructive heuristic (MRBCH) is proposed to solve the formulated sensor–weapon–target assignment (S-WTA) problem. MRBCH exploits the marginal return of each sensor–weapon–target triplet and dynamically updates the threat value of all targets. It relies only on simple lookup operations to choose each assignment triplet, thus resulting in very low computational complexity. For performance evaluation, we build a general Monte Carlo simulation-based S-WTA framework. Furthermore, we employ a random sampling method and an extension of the state-of-the-art algorithm Swt_opt as competitors. The computational results show that MRBCH consistently performs very well in solving S-WTA instances of different scales, and it can generate assignment schemes much more efficiently than its competitors. [ABSTRACT FROM AUTHOR]

The Lovász Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of "bad" events, with positive probability. A series of results have provided algorithms to efficiently construct structures whose existence is non-constructively guaranteed by the LLL, culminating in the recent breakthrough of Moser and Tardos [2010] for the full asymmetric LLL. We show that the output distribution of the Moser-Tardos algorithm well-approximates the conditional LLL-distribution, the distribution obtained by conditioning on all bad events being avoided. We show how a known bound on the probabilities of events in this distribution can be used for further probabilistic analysis and give new constructive and nonconstructive results. [ABSTRACT FROM AUTHOR]

Description logics (DLs) and rules are formalisms that emphasize different aspects of knowledge representation: whereas DLs are focused on specifying and reasoning about conceptual knowledge, rules are focused on nonmonotonic inference. Many applications, however, require features of both DLs and rules. Developing a formalism that integrates DLs and rules would be a natural outcome of a large body of research in knowledge representation and reasoning of the last two decades; however, achieving this goal is very challenging and the approaches proposed thus far have not fully reached it. In this paper, we present a hybrid formalism of MKNF+ knowledge bases, which integrates DLs and rules in a coherent semantic framework. Achieving seamless integration is nontrivial, since DLs use an open-world assumption, while the rules are based on a closed-world assumption. We overcome this discrepancy by basing the semantics of our formalism on the logic of minimal knowledge and negation as failure (MKNF) by Lifschitz. We present several algorithms for reasoning with MKNF+ knowledge bases, each suitable to different kinds of rules, and establish tight complexity bounds. [ABSTRACT FROM AUTHOR]

Set constraints form a constraint system where variables range over the domain of sets of trees. They give a natural formalism for many problems in program analysis. Syntactically, set constraints are conjunctions of inclusions between expressions built over variables, constructors (constants and function symbols from a given signature) and a choice of set operators that defines the specific class of set constraints. In this article, we are interested in the class of set constraints with projections, which is the class with all Boolean operators (union, intersection and complement) and projections that in program analysis directly correspond to type destructors. We prove that the problem of existence of a solution of a system of set constraints with projections is in NEXPTIME, and thus that it is NEXPTIME-complete. [ABSTRACT FROM AUTHOR]

XPath is a prominent W3C standard for navigating XML documents that has stimulated a lot of research into query answering and static analysis. In particular, query containment has been studied extensively for fragments of the 1.0 version of this standard, whereas little is known about query containment in (fragments of) the richer language XPath 2.0. In this article, we consider extensions of Core XPath, the navigational core of XPath 1.0, with operators that are part of or inspired by XPath 2.0: path intersection, path equality, path complementation, for-loops, and transitive closure. For each combination of these operators, we determine the complexity of query containment, both with and without DTDs. It turns out to range from EXPTIME (for extensions with path equality) and 2-EXPTIME (for extensions with path intersection) to non-elementary (for extensions with path complementation or for-loops). In almost all cases, adding transitive closure on top has no further impact on the complexity. We also investigate the effect of dropping the upward and/or sibling axes, and show that this sometimes leads to a reduction in complexity. Since the languages we study include negation and conjunction in filters, our complexity results can equivalently be stated in terms of satisfiability. We also analyze the above languages in terms of succinctness. [ABSTRACT FROM AUTHOR]

We establish the first polynomial time-space lower bounds for satisfiability on general models of computation. We show that for any constant c less than the golden ratio there exists a positive constant d such that no deterministic random-access Turing machine can solve satisfiability in time nc and space nd, where d approaches 1 when c does. On conondeterministic instead of deterministic machines, we prove the same for any constant c less than √2. Our lower bounds apply to nondeterministic linear time and almost all natural NP-complete problems known. In fact, they even apply to the class of languages that can be solved on a nondeterministic machine in linear time and space n1/c. Our proofs follow the paradigm of indirect diagonalization. We also use that paradigm to prove time-space lower bounds for languages higher up in the polynomial-time hierarchy. [ABSTRACT FROM AUTHOR]

Discusses the use of standard resolution theorem for testing order locality and transforming non-local clause sets into local ones. Use of saturate system to establish complexity bounds for a number of non-trivial entailment problems; Capability of order locality to be used as a proof-theoretic analysis of the structural properties of logical calculi; Significance of the order locality analysis.

Presents a nontrivial general lower bound on the average-case running time of Shellsort. Use of Kolgorov complexity; Details on Shellsort computation; Theorems on Shellsort algorithm.

This paper aims to develop a recovery planning approach in a three-tier manufacturing supply chain, which has a single supplier, manufacturer, and retailer under an imperfect production environment, in which we consider three types of sudden disturbances: demand fluctuation, and disruptions to production and raw material supply, which are not known in advance. Firstly, a mathematical model is developed for generating an ideal plan under imperfect production for a finite planning horizon while maximizing total profit, and then we re-formulate the model to generate the recovery plan after happening of each sudden disturbance. Considering the high commercial cost and computational intensity and complexity of this problem, we propose an efficient heuristic, to obtain a recovery plan, for each disturbance type, for a finite future period, after the occurrence of a disturbance. The heuristic solutions are compared with a standard solution technique for a considerable number of random test instances, which demonstrates the trustworthy performance of the developed heuristics. We also develop another heuristic for managing the combined effects of multiple sudden disturbances in a period. Finally, a simulation approach is proposed to investigate the effects of different types of disturbance events generated randomly. We present several numerical examples and random experiments to explicate the benefits of our developed approaches. Results reveal that in the event of sudden disturbances, the proposed mathematical and heuristic approaches are capable of generating recovery plans accurately and consistently. [ABSTRACT FROM AUTHOR]