Search

In the path version of the Travelling Salesman Problem (Path-TSP), a salesman is looking for the shortest Hamiltonian path through a set of n cities. The salesman has to start his journey at a given city s , visit every city exactly once, and finally end his trip at another given city t. In this paper we show that a special case of the Path-TSP with a Demidenko distance matrix is solvable in polynomial time. Demidenko distance matrices fulfill a particular condition abstracted from the convex Euclidian special case by Demidenko (1979) as an extension of an earlier work of Kalmanson (1975). We identify a number of crucial combinatorial properties of the optimal solution and design a dynamic programming approach with time complexity O (n 6). [ABSTRACT FROM AUTHOR]

The max-plus algebra R ∪ { − ∞ } is defined in terms of a combination of the following two operations: addition a ⊕ b : = max ⁡ (a , b) and multiplication a ⊗ b : = a + b. In this study, we propose a new method to characterize the set of all solutions of a max-plus two-sided linear system A ⊗ x = B ⊗ x. We demonstrate that the minimum "min-plus" linear subspace containing the "max-plus" solution space can be computed by applying the alternating method, which is a well-known algorithm to compute single solutions of two-sided systems. Further, we derive a sufficient condition for the "min-plus" and "max-plus" subspaces to be identical. The computational complexity of the algorithm presented in this study is pseudo-polynomial. [ABSTRACT FROM AUTHOR]

This paper tackles high computational complexity in using Euclidean distance for residential load profiles (RLPs) similarity by proposing a three-stage incremental segmented slope clustering framework. The first two stages involve static clustering, where we obtain typical residential load profiles through piecewise slope clustering. In the third stage, dynamic clustering is performed based on the slope similarity of RLPs. This method enhances clustering performance and reduces computation cost, outperforming various benchmarks, with simulation results confirming the framework's effectiveness. [ABSTRACT FROM AUTHOR]

Mathematical morphology and convolution operators are two different methods to extract the characteristics and structures of images. Over the past decades, Deep Convolutional Neural Networks (DCNN) have been proven to be more powerful than traditional image-processing approaches. In this paper, we propose a novel structure called Deep Hybrid Neural Network (DHNN) by taking advantage of the convolution and morphological neural layers. Its practical application to polyp detection in medical images is illustrated. For experimental completeness, we adopt nine polyp image datasets, including publicly available data and our own collected data. For performance comparisons, we select three backbone models. Experimental results show that our DHNN achieves the best performance in comparisons in terms of computational complexity and accurate performance. [ABSTRACT FROM AUTHOR]

Given an integer partition of n , we consider the impartial combinatorial game LCTR in which moves consist of removing either the left column or top row of its Young diagram. We show that for both normal and misère play, the optimal strategy can consist mostly of mirroring the opponent's moves. We also establish that both LCTR and Downright are domestic as well as returnable, and on the other hand neither tame nor forced. For both games, those structural observations allow for computing the Sprague–Grundy value any position in O (log (n)) time, assuming that the time unit allows for reading an integer, or performing a basic arithmetic operation. This improves on the previously known bound of O (n) due to Ilić (2019). We also cover some other complexity measures of both games, such as state–space complexity, and number of leaves and nodes in the corresponding game tree. • We study the impartial combinatorial game LCTR and its misère variant Downright. • There are two allowable moves: remove the left column or top row of a Young diagram. • For both normal and misère play, the optimal move often mirrors the oppononent. • Both LCTR and Downright are domestic and returnable, and neither tame nor forced. • We describe an algorithm to compute the Sprague–Grundy value in O (log (n)) time. • We cover state–space complexity, and number of leaves and nodes in the game tree. [ABSTRACT FROM AUTHOR]

The recent developments in quantum technology have opened up new opportunities for machine learning algorithms to assist the healthcare industry in diagnosing complex health disorders, such as heart disease. In this work, we summarize the effectiveness of QuEML in heart disease prediction. To evaluate the performance of QuEML against traditional machine learning algorithms, the Kaggle heart disease dataset was used which contains 1190 samples out of which 53% of samples are labeled as positive samples and rest 47% samples are labeled as negative samples. The performance of QuEML was evaluated in terms of accuracy, precision, recall, specificity, F1 score, and training time against traditional machine learning algorithms. From the experimental results, it has been observed that proposed quantum approaches predicted around 50.03% of positive samples as positive and an average of 44.65% of negative samples are predicted as negative whereas traditional machine learning approaches could predict around 49.78% of positive samples as positive and 44.31% of negative samples as negative. Furthermore, the computational complexity of QuEML was measured which consumed average of 670 µs for its training whereas traditional machine learning algorithms could consume an average 862.5 µs for training. Hence, QuEL was found to be a promising approach in heart disease prediction with an accuracy rate of 0.6% higher and training time of 192.5 µs faster than that of traditional machine learning approaches. [ABSTRACT FROM AUTHOR]

For the characteristics of channel instability in wireless sensor networks, this paper proposes an intrusion detection algorithm based on FedAvg (federated averaging) and XGBoost (extreme gradient boosting) wireless sensor networks using fog computing architecture. First, the network edge is extended by introducing fog computing nodes to reduce the communication delay. It reduces the transmission bandwidth and privacy leakage risk while improving the accuracy of jointly learned global and local models. Then, the histogram-based approximation calculation method is improved to adapt to the unbalanced data characteristics of wireless sensor networks. Finally, by introducing TOP-K gradient selection, the number of model parameter uploads is minimized, and the efficiency of model parameter interaction is improved. The experimental results show that this algorithm has superior detection performance and low energy consumption. It is also compared with other algorithms to demonstrate the high detection rate and low computational complexity of this algorithm. [ABSTRACT FROM AUTHOR]

This paper studies the state estimation for cyber‐physical systems with multiple channels under joint Denial‐of‐Service and deception attacks. We show that the optimal estimator (OE) cannot be implemented in practice, as its computational complexity exponentially grows with respect to time. Then, we develop a centralized approximate optimal estimator (AOE) by using a generalized pseudo‐Bayesian algorithm. This AOE is not only computationally efficient, but also features theoretically guaranteed performance and stability. Specifically, it is proved when the attack success rate is less than a threshold value, both the OE and the AOE are stable, and the averaged performance deviation between the OE and the proposed AOE remains bounded. Finally, simulation examples are provided to illustrate the obtained results. [ABSTRACT FROM AUTHOR]

This article studies the two‐layer leader‐follower optimal affine formation maneuver (AFM) control problem for multiple unmanned surface vessels (USV). The basic idea of the developed two‐layer control framework is to realize the time‐varying formation for the leader group in advance, and then let the follower USVs agilely respond to the target formation affinely localized by leaders. To realize this goal, a time‐varying formation reference system is first synthesized to describe leaders' target formation in the affine map of the nominal configuration. The reference system is set up by virtual vessel velocity command and unrotated geometric command, which make it possesses an intuitive application structure for operators to plan AFM commands in real‐time sensed surrounding environments. Then, by means of optimized backstepping design and the adaptive dynamic programming technique, actor‐only reinforcement learning controllers are established for USVs in both two layers to realize the optimal target formation tracking objective. For the proposed optimal controllers, the persistent excitation condition that is required by common optimal control schemes is also removed, which endows the presented scheme with lower computational complexity. Finally, theoretical analysis and simulation results illustrate the closed‐loop stability and the effectiveness of the presented scheme. [ABSTRACT FROM AUTHOR]

For supervised learning problems, a unified kernel sparse representation framework is proposed. It is applicable to almost all supervised learners in order to look for kernel representation hypersurface, such as SVM-type or TSVM-type models. Focusing on classification and regression problems in supervised learning, three concrete sparse TSVM-type models are constructed by incorporating specific regularization terms and loss functions. Our methods involve selecting L representative points from the entire training set using the GRPS algorithm. The sparsization parameter L significantly reduces computational complexity by avoiding the need to process all training points. As a result, both the optimization problems and prediction computation costs for new instances are reduced. By comparing our sparse TSVMs with the methods based on the sparse norm regularization terms, our sparsization parameter L is more intuitional than their regularization parameter. Interestingly enough, the numerical experiments on four artificial datasets and 20 benchmark datasets demonstrate that our methods require less prediction time and exhibit better generalization ability when the sparsization parameter L is taken as a small value, i.e., L ≪ N . [ABSTRACT FROM AUTHOR]

H.266/Versatile Video Coding (VVC) is the most recent video coding standard developed by the Joint Video Experts Team (JVET). The quad-tree with nested multi-type tree (QTMT) architecture that improves the compression performance of H.266/VVC is introduced. Moreover, H.266/VVC contains a greater number of intra-prediction modes than H.265/High Efficiency Video Coding (HEVC), totalling 67. However, these lead to extremely the coding computational complexity. To cope with the above issues, a fast intra-coding unit (CU) size decision method and a fast intra-prediction mode decision method are proposed in this paper. Specifically, the trained Support Vector Machine (SVM) classifier models are utilized for determining CU partition mode in a fast CU size decision scheme. Furthermore, the quantity of intra-prediction modes added to the RDO mode set decreases in a fast intra-prediction mode decision scheme based on the improved search step. Simulation results illustrate that the proposed overall algorithm can decrease 55.24% encoding runtime with negligible BDBR. [ABSTRACT FROM AUTHOR]

Recent advancements in autonomous mobile robots have led to significant progress in area coverage tasks. However, challenges persist in optimizing the efficiency and computational complexity of complete coverage path planner (CCPP) algorithms for multi-robot systems, particularly in scenarios requiring revisiting or a double pass in specific locations, such as cleaning robots addressing spilled consumables. This paper presents an innovative approach to tackling the double-pass complete coverage problem using an autonomous inter-reconfigurable robot path planner. Our solution leverages a modified Glasius bio-inspired neural network (GBNN) to facilitate double-pass coverage through inter-reconfiguration between two robots. We compare our proposed algorithm with traditional multi-robot path planning in a centralized system, demonstrating a reduction in algorithm iterations and computation time. Our experimental results underscore the efficacy of the proposed solution in enhancing the efficiency of area coverage tasks. Furthermore, we discuss the implementation details and limitations of our study, providing insights for future research directions in autonomous robotics. [ABSTRACT FROM AUTHOR]

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

Multi-view stereo plays an important role in 3D reconstruction but suffers from low reconstruction efficiency and has difficulties reconstructing areas with low or repeated textures. To address this, we propose MVP-Stereo, a novel multi-view parallel patchmatch stereo method. MVP-Stereo employs two key techniques. First, MVP-Stereo utilizes multi-view dilated ZNCC to handle low texture and repeated texture by dynamically adjusting the matching window size based on image variance and using a portion of pixels to calculate matching costs without increasing computational complexity. Second, MVP-Stereo leverages multi-scale parallel patchmatch to reconstruct the depth map for each image in a highly efficient manner, which is implemented by CUDA with random initialization, multi-scale parallel spatial propagation, random refinement, and the coarse-to-fine strategy. Experiments on the Strecha dataset, the ETH3D benchmark, and the UAV dataset demonstrate that MVP-Stereo can achieve competitive reconstruction quality compared to state-of-the-art methods with the highest reconstruction efficiency. For example, MVP-Stereo outperforms COLMAP in reconstruction quality by around 30 % of reconstruction time, and achieves around 90 % of the quality of ACMMP and SD-MVS in only around 20 % of the time. In summary, MVP-Stereo can efficiently reconstruct high-quality point clouds and meet the requirements of several photogrammetric applications, such as emergency relief, infrastructure inspection, and environmental monitoring. [ABSTRACT FROM AUTHOR]

The complementary characteristics of SAR and optical images are beneficial in improving the accuracy of land cover classification. Deep learning-based models have achieved some notable results. However, how to effectively extract and fuse the unique features of multi-modal images for pixel-level classification remains challenging. In this article, a two-branch supervised semantic segmentation framework without any pretrained backbone is proposed. Specifically, a novel symmetric attention module is designed with improved strip pooling. The multiple long receptive fields can better perceive irregular objects and obtain more anisotropic contextual information. Meanwhile, to solve the semantic absence and inconsistency of different modalities, we construct a multi-scale fusion module, which is composed of atrous spatial pyramid pooling, varisized convolutions and skip connections. A joint loss function is introduced to constrain the backpropagation and reduce the impact of class imbalance. Validation experiments were implemented on the DFC2020 and WHU-OPT-SAR datasets. The proposed model achieved the best quantitative values on the metrics of OA, Kappa and mIoU, and its class accuracy was also excellent. It is worth mentioning that the number of parameters and the computational complexity of the method are relatively low. The adaptability of the model was verified on RGB–thermal segmentation task. [ABSTRACT FROM AUTHOR]

Arc faults are the main cause of electrical fires according to national fire data statistics. Intensive studies of artificial intelligence-based arc fault detection methods have been carried out and achieved a high detection accuracy. However, the computational complexity of the artificial intelligence-based methods hinders their application for arc fault detection devices. This paper proposes a lightweight arc fault detection method based on the discrimination of a novel feature for lower current distortion conditions and the Adam-optimized BP neural network for higher distortion conditions. The novel feature is the pulse signal number per unit cycle, reflecting the zero-off phenomena of the arc current. Six features, containing the novel feature, are chosen as the inputs of the neural network, reducing the computational complexity. The model achieves a high detection accuracy of 99.27% under various load types recommended by the IEC 62606 standard. Finally, the proposed lightweight method is implemented on hardware based on the STM32 series microcontroller unit. The experimental results show that the average detection accuracy is 98.33%, while the average detection time is 45 ms and the average tripping time is 72–201 ms under six types of loads, which can fulfill the requirements of real-time detection for commercial arc fault detection devices. [ABSTRACT FROM AUTHOR]

In this letter, a new learnable binary MIMO detection algorithm in massive MIMO systems with one‐bit analog‐to‐digital converters is proposed. A negative penalty is introduced to transform a non‐convex constraint to a convex box constraint and a learnable iterative algorithm is presented based on inexact alternating direction methods of multipliers. The proposed MIMO detection method performs better than the existing binary MIMO detection methods even with lower computational complexity. [ABSTRACT FROM AUTHOR]

Analogue gravity helps to find some gravitational systems which are similar to the evolution of perturbation in condensed matter systems. These analogies provide a very good tool for either side. In other words, some aspects of gravity could be simulated in condensed matter laboratories. In this study, we find an interpretation for computational complexity in condensed matter systems in terms of the flux density of the fluid and the analogue of the uncertainty principle as the Lloyd bound. We show that the Lloyd bound is reduced to the shear viscosity to entropy ratio (SVER). It has been revealed that the analogue gravity is a fluid located at a time-like finite cut-off surface (call it the bulk fluid) and we found the relation between SVER of the analogue gravity and the boundary fluid. Then we see that whenever the Kovtun–Son–Starinet (KSS) bound is satisfied in the boundary fluid, the KSS bound could be either satisfied in the bulk fluid or not; in addition, when the KSS bound is violated in the boundary fluid, then the KSS bound is violated in the bulk fluid. In other words the satisfaction of the KSS bound in the boundary fluid is a necessary condition for the satisfaction of the KSS bound in the bulk fluid. [ABSTRACT FROM AUTHOR]

Some theories of rational belief assume that beliefs should be closed under conjunction. I motivate the rejection of the conjunction closure, and point out that the consequences of this rejection are not as severe as it is usually thought. An often raised objection is that without the conjunction closure people are unable to reason. I outline an approach in which we can – in usual cases – reason using conjunctions without accepting the closure in its whole generality. This solution is based on the notion of confidence levels , which can be defined using probabilities. Moreover, on this approach, reasoning has a scalable computational complexity adaptable to cognitive abilities of both rationally bounded and perfectly rational agents. I perform a simulation to assess its error rate, and compare it to reasoning with conjunction closure. [ABSTRACT FROM AUTHOR]

We study the computational complexity of the problem #IndSub(Φ) of counting k-vertex induced subgraphs of a graph G that satisfy a graph property Φ. Our main result establishes an exhaustive and explicit classification for all hereditary properties, including tight conditional lower bounds under the Exponential Time Hypothesis (ETH): - If a hereditary property Φ is true for all graphs, or if it is true only for finitely many graphs, then #IndSub(Φ) is solvable in polynomial time. - Otherwise, #IndSub(Φ) is #W[1]-complete when parameterised by k, and, assuming ETH, it cannot be solved in time f(k)µ/G/o(k) for any function f. This classification features a wide range of properties for which the corresponding detection problem (as classified by Khot and Raman [TCS 02]) is tractable but counting is hard. Moreover, even for properties which are already intractable in their decision version, our results yield significantly stronger lower bounds for the counting problem. As additional result, we also present an exhaustive and explicit parameterised complexity classification for all properties that are invariant under homomorphic equivalence. By covering one of the most natural and general notions of closure, namely, closure under vertex-deletion (hereditary), we generalise some of the earlier results on this problem. For instance, our results fully subsume and strengthen the existing classification of #IndSub(Φ) for monotone (subgraph-closed) properties due to Roth, Schmitt, and Wellnitz [FOCS 20]. [ABSTRACT FROM AUTHOR]

We study the problem of approximating the distances in an undirected weighted graph G by the distances in trees based on the notion of stretch. Focusing on decentralized models of computation such as the CONGEST, PRAM, and semi-streaming models, our main results are as follows: (1) We develop a simple randomized algorithm that constructs a spanning tree such that the expected stretch of every edge is O(log³ n), where n is the number of nodes in G. If G is unweighted, then this algorithm can be implemented to run in O(hop(G)) rounds in the CONGEST model, where hop(G) is the hop-diameter of G; thus our algorithm is asymptotically optimal in this case. In the weighted case, the run-time of the algorithm matches the currently best known bound for exact single source shortest path (SSSP) computations, which despite recent progress is still separated from the lower bound of Ω(√n + hop(G)) by polynomial factors. A naive attempt to replace exact SSSP computations with approximate ones in order to improve the complexity in the weighted case encounters a fundamental challenge, as the underlying decomposition technique fails to work under distance approximation. (2) We overcome this obstacle by developing a technique termed blurry ball growing. This technique, in combination with a clever algorithmic idea of Miller, Peng, and Xu (SPAA 2013), allows us to obtain low diameter graph decompositions with small edge cutting probabilities based solely on approximate SSSP computations. (3) Using these decompositions, we in turn obtain metric tree embedding algorithms in the vein of the celebrated work of Bartal (FOCS 1996), whose computational complexity is optimal up to polylogarithmic factors not only in the CONGEST model but also in the PRAM and semi-streaming models. Our embeddings have the additional useful property that the tree can be mapped back to the original graph such that each edge is "used" only logarithmically many times. This property is of interest for capacitated problems and for simulating CONGEST algorithms on the tree into which the graph is embedded. [ABSTRACT FROM AUTHOR]

We consider effective preconditioners for solving Laplacians of general weighted graphs. Theoretically, spectral sparsifiers (SSs) provide preconditioners of optimal computational complexity. However, they are not easy to use for real-world applications due to implementation complications. Multigrid methods, on the contrary, are computationally efficient but lack theoretical justification. To bridge the gap between theory and practice, we adopt ideas of multigrid and SS methods and proposed preconditioners that can be used in practice with theoretical guarantees. We expand the original graph based on a multilevel structure to obtain an equivalent expanded graph. Although the expanded graph has a low diameter, a favorable property for constructing SSs, it has negatively weighted edges, which is an unfavorable property for SSs. We design an algorithm to properly eliminate the negatively weighted edges and prove that the resulting expanded graph with positively weighted edges is spectrally equivalent to the expanded graph and, thus, the original graph. Due to the low-diameter property of the positively weighted expanded graph preconditioner (PEGP), existing algorithms for finding SSs can be easily applied. To demonstrate the advantage of working with PEGP, we propose a type of SS, the multilevel graph sparsifier preconditioner (MGSP), that can be constructed in an easy and deterministic manner. We provide some preliminary numerical experiments to verify our theoretical findings and illustrate the practical effectiveness of PEGP and MGSP in real-world applications. [ABSTRACT FROM AUTHOR]

Hierarchical matrices provide a powerful representation for significantly reducing the computational complexity associated with dense kernel matrices. For example, the fast multipole method (FMM) and its variants are highly efficient when the kernel function is related to fundamental solutions of classical elliptic PDEs. For general kernel functions, interpolation-based methods are widely used for the efficient construction of hierarchical matrices. In this paper, we present a fast hierarchical data reduction (HiDR) procedure with O(n) complexity for the memoryefficient construction of hierarchical matrices with nested bases where n is the number of data points. HiDR aims to reduce the given data in a hierarchical way so as to obtain O(1) representations for all nearfield and farfield interactions. Based on HiDR, a linear complexity H² matrix construction algorithm is proposed. The use of data-driven methods enables better efficiency than other general-purpose methods and flexible computation without accessing the kernel function. Experiments demonstrate significantly improved memory efficiency of the proposed data-driven method compared to interpolation-based methods over a wide range of kernels. For the Coulomb kernel, the proposed general-purpose algorithm offers competitive performance compared to FMM and its variants, such as PVFMM. The data-driven approach not only works for general kernels but also leads to much smaller precomputation costs compared to PVFMM. [ABSTRACT FROM AUTHOR]

The object of the study is the process of forming control decisions to ensure the operation of the ground-air communication network routing subsystem based on neural network algorithms. The carried-out research is based on the application of the numerical-analytical approach to the selection of modern scientific and applied solutions for building management models for promising Ad-Hoc communication networks. In the Google Collab simulation environment, using the Python programming language, it was possible: firstly, to simulate the operation of a ground-to-air communication network based on previously obtained models and a routing process management system based on the FA-OSELM algorithm. Secondly, in accordance with the scenario of route construction and maintenance described in the article, to experimentally determine the communication metrics of the proposed method of intelligent routing of the ground-air Ad-Hoc special-purpose network, in order to assess its efficiency, adequacy and reliability of the results obtained. Thus, in order to evaluate the effectiveness of the proposed solutions, a comparative analysis of the application of three existing routing methods (FLCA, Q-Routing, Neuro Routing) used in Ad-Hoc networks relative to the developed method was conducted. The result of the experiment showed that the proposed routing method MAODV-FA-OSELM provides significant advantages over analogs. Thus, the method exhibits the best network throughput (2.12e+06), the lowest average network latency (0.12), the lowest packet loss (6.32), the lowest bit error rate (2.41), and the lowest overhead (0.10e+06). However, it should be noted that a promising direction of further research may be the study of the computational complexity of the routing management process and the determination of the minimum allowable representative sample of initial data to ensure online decision-making. [ABSTRACT FROM AUTHOR]

The author analyses new methods, approaches, and ideas for further development of image encoding to increase informativeness and reduce computational complexity. An architecture (a set of adaptive encoding modes with minimal computational expenses for selecting and switching between them) for a simplified high-speed codec is developed. Simple universal algorithms for predicting pixel values based on external data and using values of neighboring blocks are provided. A modification of MSE (shifted MSE) is proposed. A one-norm simplified cosine transform of order 16 with low computational complexity is proposed. A new algorithm for adaptive use of transforms of different types and orders depending on the compression coefficient is given. [ABSTRACT FROM AUTHOR]

Voltage sags resulting from symmetrical or asymmetrical faults pose a significant threat to power quality. In response to this challenge, a voltage sag loss assessment method based on a two-stage Taguchi quality perspective approach is proposed to address the quantitative analysis of voltage sag economic losses. Initially, using the Taguchi quality perspective method, single-index quality loss functions are separately established for voltage sag magnitude and fault duration. Subsequently, by introducing a comprehensive load tolerance curve, sensitivity parameters within the quality loss function are accurately calculated. This yields a deterministic model for voltage sag assessment. Building upon this, the relative impact of the two indices on voltage sag loss is evaluated using the quality loss function. Consequently, a comprehensive loss model under the influence of multiple indices is formed by integrating two single-index evaluation models. The simulation results indicate that this method can effectively assess the economic losses of voltage sags under the combined influence of multiple factors. Compared to the original economic loss assessment method, it improves quantitative accuracy by approximately 3.72%. Moreover, the method reduces the computational complexity of loss assessment through the consolidation of intervals with similar sensitivity parameters. [ABSTRACT FROM AUTHOR]

In this study, an innovative approach that combines least square support vector regression (LSSVR) with uncertainty theory to enhance its performance in dealing with low-quality or imprecise data from real-world be proposed. The resulting model, called uncertain least square support vector regression (ULSSVR), incorporates chance constraints and simplified parameter selection, which are critical to handle imprecise observations. A numerical algorithm called the conjugate residual method (CR) is introduced to reduce the computational complexity of the model solution. The experimental results using both small and medium-sized datasets demonstrate the superior performance of ULSSVR in terms of prediction accuracy and generalization ability compared to other models such as uncertain support vector regression (USVR), uncertain linear lodel, uncertain polynomial model, and uncertain growth models. ULSSVR not only improves prediction accuracy by at least 28.49% but also demonstrates faster computational speed. Overall, ULSSVR presents a promising solution for data science and internet applications where dealing with imprecise and low-quality data is a common challenge. [ABSTRACT FROM AUTHOR]

Cluster analysis is an important method for data analysis, which is also widely used in remote sensing image classification. An effective clustering algorithm is proposed for the uncertainty caused by the overlap between categories in pattern data and remote sensing images. First, an improved PCM (Possibilistic C-means) algorithm based on distance of cluster center (dc-PCM) is proposed to solve the clustering consistency problem of PCM algorithm. Then, based on dc-PCM algorithm, an improved interval type-2 probabilistic c-means clustering algorithm (IT2-dcPCM) is proposed for interclass maximization. The computational complexity of the proposed algorithm is analyzed, and its performance is evaluated by three data sets, two groups of images segmentation and two groups of remote sensing image classification experiments. The results show that IT2-dcPCM algorithm can assign proper membership degrees to clustering samples, and it has good performance in image segmentation and remote sensing image classification with serious spectral aliasing. [ABSTRACT FROM AUTHOR]

Conversational recommender systems use natural language conversations to elicit user preferences and recommend items proactively. Existing methods based on graph neural networks have been proven to be effective in exploiting knowledge graphs. However, node positions are often treated as constants, which leads to the neglect of graph connectivity due to fuzzy processing. In addition, although the transformer has significant advantages in understanding the text, its secondary computational complexity may be incapable when dealing with long texts. In order to solve these problems, we propose an additive positional conversational recommender model called APCR. This model converts the pair product of transformer into a linear operation, and uses the Laplacian eigenvector to build a location graph. The extended graph neural network captures the topology structure of the location knowledge graph. Specifically, we design an encoder based on additive attention to break through the bottleneck of long text. Furthermore, we develop a recommendation model based on a positional graph neural network to match items with dialogue context, thereby capturing the graph topology. Extensive experiments on the REDIAL dataset show significant improvements in our proposed model over the state-of-the-art methods in recommendation and dialogue generation evaluations. [ABSTRACT FROM AUTHOR]

The recent development of multidimensional ultrafast spectroscopy techniques calls for the introduction of computational schemes that allow for the simulation of such experiments and the interpretation of the corresponding results from a microscopic point of view. In this work, we present a general and efficient first-principles scheme to compute two-dimensional electronic spectroscopy maps based on real-time time-dependent density-functional theory. The interface of this approach with the Ehrenfest scheme for molecular dynamics enables the inclusion of vibronic effects in the calculations based on a classical treatment of the nuclei. The computational complexity of the simulations is reduced by the application of numerical advances such as branching techniques, undersampling, and a novel reduced phase cycling scheme, applicable for systems with inversion symmetry. We demonstrate the effectiveness of this method by applying it to prototypical molecules such as benzene, pyridine, and pyrene. We discuss the role of the approximations that inevitably enter the adopted theoretical framework and set the stage for further extensions of the proposed method to more realistic systems. [ABSTRACT FROM AUTHOR]

This article proposes a novel lightweight attention spatiotemporal joint distribution adaptation network fault diagnosis model to address the key challenges of domain transfer and high model complexity in traditional methods. The novelty lies in 1. Using model compression techniques to reduce the complexity of the network model and improve its computational efficiency; 2. Introducing new domain adaptation and adversarial methods to solve the domain transfer problem. The effectiveness of the proposed model is verified through a transfer experiment of planetary gearbox vibration data. The experimental results show that the proposed model reduces the parameters and computational complexity to 18 % and 15 % of the original model, respectively, and has a diagnostic accuracy of over 98 % in cross-condition transfer tasks, and still maintains an accuracy of over 88 % even under high noise levels. This indicates that the proposed model is an efficient and accurate fault diagnosis model. [ABSTRACT FROM AUTHOR]

Signcryption integrates both signature and encryption schemes into single scheme to ensure both content unforgeability (authentication) and message confidentiality while reducing computational complexity. Typically, both signers (senders) and decrypters (receivers) in a signcryption scheme belong to the same public-key systems. When signers and decrypters in a signcryption scheme belong to heterogeneous public-key systems, this scheme is called a hybrid signcryption scheme which provides more elastic usage than typical signcryption schemes. In recent years, a new kind of attack, named side-channel attack, allows adversaries to learn a portion of the secret keys used in cryptographic algorithms. To resist such an attack, leakage-resilient cryptography has been widely discussed and studied while a large number of leakage-resilient schemes have been proposed. Also, numerous hybrid signcryption schemes under heterogeneous public-key systems were proposed, but none of them possesses leakage-resilient property. In this paper, we propose the first hybrid signcryption scheme with leakage resilience, called leakage-resilient hybrid signcryption scheme, in heterogeneous public-key systems (LR-HSC-HPKS). Security proofs are demonstrated to show that the proposed scheme provides both authentication and confidentiality against two types of adversaries in heterogeneous public-key systems. [ABSTRACT FROM AUTHOR]

Three-dimensional voxel models are widely applied in various fields such as 3D imaging, industrial design, and medical imaging. The advancement of 3D modeling techniques and measurement devices has made the generation of three-dimensional models more convenient. The exponential increase in the number of 3D models presents a significant challenge for model retrieval. Currently, these models are numerous and typically represented as point clouds or meshes, resulting in sparse data and high feature dimensions within the retrieval database. Traditional methods for 3D model retrieval suffer from high computational complexity and slow retrieval speeds. To address this issue, this paper combines spatial-filling curves with octree structures and proposes a novel approach for representing three-dimensional voxel model sequence data features, along with a similarity measurement method based on symbolic operators. This approach enables efficient similarity calculations and rapid dimensionality reduction for the three-dimensional model database, facilitating efficient similarity calculations and expedited retrieval. [ABSTRACT FROM AUTHOR]

Transformers are the cornerstone of natural language processing and other much more complicated sequential modelling tasks. The training of these models, however, requires an enormous number of computations, with substantial economic and environmental impacts. An accurate estimation of the computational complexity of training would allow us to be aware in advance about the associated latency and energy consumption. Furthermore, with the advent of forward learning workloads, an estimation of the computational complexity of such neural network topologies is required in order to reliably compare backpropagation with these advanced learning procedures. This work describes a mathematical approach, independent from the deployment on a specific target, for estimating the complexity of training a transformer model. Hence, the equations used during backpropagation and forward learning algorithms are derived for each layer and their complexity is expressed in the form of MACCs and FLOPs. By adding all of these together accordingly to their embodiment into a complete topology and the learning rule taken into account, the total complexity of the desired transformer workload can be estimated. [ABSTRACT FROM AUTHOR]

This paper is aimed at using a lookup table method to improve the scalar multiplication performance of elliptic curve cryptography. The lookup table must be divided into two polynomials and requires two iterations of point doubling operation, for which negation operations are needed. It is well known that an inversion operation requires a lot of multiplication time. The advantage of this paper is that we are able to reduce one inverse element calculation for this problem and also improve the basic operations of finite fields through segmentation methods. If the normal basis method is used in the design of the inverse element operation, it must be converted to the normal basis through the standard basis. However, the conversion process requires a lot of matrix operations. Though the anti-element operation has good speed performance, it also increases the computational complexity. Using number theory and grouping methods will greatly improve the performance of inverse element operations. With application of the two-time point doubling operation in the hardware implementation, the developed approach reduces the computing time by 48% as compared with the conventional approach. The computational time of the scalar multiplication using the presented method is further improved by 67% over the traditional algorithm with only an area increase of 12%. Finally, the proposed lookup table-based technique can be utilized for software and hardware implementation, as the developed arithmetic operations are simple and are consistent in their execution. [ABSTRACT FROM AUTHOR]

In spine imaging, efficient automatic segmentation is crucial for clinical decision‐making, yet current models increase accuracy at the expense of elevated parameter counts and computational complexity, complicating integration with contemporary medical devices. Addressing identified challenges, this research introduces LE‐NeXt, a spine segmentation framework utilizing multi‐dimensional spatial attention and multi‐scale feature extraction, optimizing the architecture via convolution and MLP. It integrates lightweight convolutions and attention mechanisms within an encoder‐decoder model, enhancing stage‐specific feature extraction while ensuring efficiency. Experimental analyses on VerSe and SpineWeb datasets demonstrate that LE‐NeXt outperforms the lightweight U‐NeXt, enhancing IoU accuracy from 87.7 to 89.8 on VerSe, and exceeds the performance of established networks such as U‐Net and its variants. Significantly, on SpineWeb, LE‐NeXt not only surpasses Trans U‐Net in accuracy but also achieves a considerable reduction in both parameter count and computational complexity. These results emphasize LE‐NeXt's effectiveness in improving segmentation precision efficiently, optimally balancing computational efficiency and accuracy. [ABSTRACT FROM AUTHOR]

Accurate skin lesion segmentation (SLS) plays an essential role in the computer‐aided diagnosis of skin diseases, for example, melanomas. However, the automated SLS is challenging due to variations in the nature of skin diseases, particularly the ambiguities of boundaries of skin lesion areas (SLAs) and occlusions by hairs. Though many deep learning models, represented by UNet, have been successfully applied to the SLS over the past years, most suffer from inaccurate SLA segmentation with heavy model parameters and slow inferencing speed, hindering their practical applications. To address these challenges, a lightweight SLS network based on structural re‐parameterization and parallel axial shift multilayer perceptron (MLP), called SRP&PASMLP‐Net, is proposed to achieve powerful segmentation performance with fast inference ability. Specifically, a kind of diverse convolution module, the Re‐parameterization Diversity Convolution (RDC) block, is proposed in the shallow stage of the segmentation network to enrich the feature space. The inference is performed by structural re‐parameterization techniques to decouple the structure at the training and inference stages, thus improving the performance of the model without any inference time cost. In addition, a parallel axial shift MLP (PASMLP) module is proposed, which captures local dependencies by axially shifting the channels of the feature map to capture the information flow from different axes and reduce the network parameters and computational complexity effectively. Extensive experimental results show that the proposed SRP&PASMLP‐Net can provide a 4‐fold improvement in the inference speed and a 17‐fold reduction in model parameters compared with the benchmark network, UNet. It outperforms the state‐of‐the‐art methods on two public datasets, that is, ISIC2018 and PH2, for the SLS. [ABSTRACT FROM AUTHOR]

Let G be a graph with n vertices and m edges. A (G) and I denote, respectively, the adjacency matrix of G and an n by n identity matrix. For a graph G, the permanent of matrix (I + A (G)) is called the permanental sum of G. In this paper, we give a relation between the Hosoya index and the permanental sum of G. This implies that the computational complexity of the permanental sum is N P -complete. Furthermore, we characterize the graphs with the minimum permanental sum among all graphs of n vertices and m edges, where n + 3 ≤ m ≤ 2 n − 3 . [ABSTRACT FROM AUTHOR]

The Philippine Sea, located at the edge of the northwestern Pacific Ocean, possesses complex seabed topography. Developing a high-precision bathymetric model for this region is of paramount importance, as it provides fundamental geoinformation essential for Earth observation and marine scientific research, including plate motion, ocean circulation, and hydrological characteristics. The gravity–geologic method (GGM), based on marine gravity anomalies, serves as an effective bathymetric prediction technique. To further strengthen the prediction accuracy of conventional GGM, we introduce the improved GGM (IGGM). The IGGM considers the effects of regional seafloor topography by employing weighted averaging to more accurately estimate the short-wavelength gravity component, along with refining the subsequent modeling of long-wavelength gravity component. In this paper, we focus on seafloor topography modeling in the Philippine Sea based on the IGGM, combining shipborne bathymetric data with the Scripps Institution of Oceanography (SIO) V32.1 gravity anomaly. To reduce computational complexity, the optimal parameter values required for IGGM are first calculated before the overall regional calculation, and then, based on the terrain characteristics and distribution of sounding data, we selected four representative local sea areas as the research objects to construct the corresponding bathymetric models using GGM and IGGM. The analysis indicates that the precision of the IGGM models in four regions is improved to varying degrees, and the optimal calculation radius is 2 ′. Based on the above finding, a high-precision 1′×1′ bathymetric model of the Philippine Sea (5–35° N, 120–150° E), known as the BAT_PS model, is constructed using IGGM. Results demonstrate that the BAT_PS model exhibits a higher overall precision compared to the General Bathymetric Chart of the Oceans (GEBCO), topo_25.1, and DTU18 models at single-beam shipborne bathymetric points. [ABSTRACT FROM AUTHOR]

With the rapid development of deep learning technology, object detection algorithms have made significant breakthroughs in the field of computer vision. However, due to the complexity and computational requirements of deep Convolutional Neural Network (CNN), these models face many challenges in practical applications, especially on resource-constrained edge devices. To address this problem, researchers have proposed many lightweight methods that aim to reduce the model size and computational complexity while maintaining high performance. The popularity of mobile devices and embedded systems has led to an increasing demand for lightweight models. However, existing lightweight methods often lead to accuracy loss, limiting their feasibility in practical applications. Therefore, how to realize the light weight of the model while maintaining high accuracy has become an urgent problem to be solved. To address this challenge, this paper proposes a lightweight YOLOv7 method based on PConv, Squeeze-and-Excitation (SE) attention mechanism and Wise-IoU (WIoU), which we refer to as YOLOv7-PSW. PConv can effectively reduce the number of parameters and computational complexity. The SE can help the model focus on important feature information, thereby improving performance. WIoU is introduced to measure the similarity between the detection box and the Ground Truth, so that the model can effectively reduce the False Positive rate. By applying these advanced techniques to the YOLOv7, we achieve a lightweight model while maintaining a high detection accuracy. Experimental results on PASCAL VOC dataset show that YOLOv7-PSW performs better than the original YOLOv7 on object detection tasks. The number of parameters is reduced by 12.3%, FLOPs is reduced by 18.86%, and the accuracy is improved by about 0.5%. While the detection accuracy is not decreased or even slightly improved, the number of FLOPs and parameters is greatly reduced, which realizes lightweight to a certain extent. The proposed method can provide new ideas and directions for the subsequent research on lightweight object detection, and is expected to promote its application on edge devices. Meanwhile, YOLOv7-PSW can also be applied to other computer vision tasks to improve its performance and efficiency. In summary, the proposed YOLOv7-PSW lightweight method realizes the light weight of the model while maintaining high accuracy. This is of great significance for promoting the application of object detection algorithms on edge devices. [ABSTRACT FROM AUTHOR]

Beamspace processing is widely applied in Direction‐of‐Arrival (DOA) estimation thanks to dimensional reduction and super‐resolution characterisations. However, the conventional atomic norm minimisation (ANM) based methods for beamspace DOA estimation are of high computational complexity for large arrays. To deal with this issue, the proposed method focuses on locating the sources in the mainlobe of the beamspace and encodes such prior information into the ANM problem without frequency‐selective constraints. The proposed method approximates the beamspace array manifold in the mainlobe sector with the truncated sector Fourier series. The theoretical analysis shows that such approximation with the properly designed fitting error relaxation on the boundary yields the low dimensional semidefinite programming (SDP) approximate implementation of the proposed ANM method and guarantees the support recovery inside the mainlobe. Furthermore, the low complexity Burer‐Monteiro factorisation based alternating direction method of multipliers method is proposed to solve the SDP problem. The complexity analysis and simulations show that the proposed method results in significant computational complexity reduction and slightly better performance compared with state‐of‐art benchmarks. [ABSTRACT FROM AUTHOR]

As an extension of spatial modulation (SM) technology, generalized spatial modulation (GSM) systems can achieve higher data transmission rates with limited spectrum resources due to activate multiple transmit antennas to send data in each time slot. Simultaneously activating multiple transmit antennas increase the difficulty of signal demodulation at the receiver in GSM systems. To reduce the high computational complexity of the maximum likelihood (ML) detection algorithm in GSM systems, a low-complexity GSM detection algorithm is proposed, which combines the iterative zero forcing (IZF) algorithm and the minimum mean square error (MMSE) equalization processing detection algorithm. Firstly, the zero forcing (ZF) algorithm is used to iteratively detect all transmit antenna combinations to obtain multiple unlikely transmit antenna indices. Then the number of search antenna combinations is reduced by removing these antenna combinations. Next, MMSE equalization detection and symbol quantification on the new search set are performed. Finally, the ML algorithm is used to estimate the transmit antenna combination and transmit symbols. The effectiveness of the proposed algorithm is verified by simulation experiments. The simulation results show that the computational complexity of the proposed algorithm is much lower than that of the ML algorithm, and the bit error rate (BER) performance is close to that of the ML algorithm. [ABSTRACT FROM AUTHOR]

Due to the large fluctuations of the boundaries and internal variations of the lesion regions in medical image segmentation, current methods may have difficulty capturing sufficient global contexts effectively to deal with these inherent challenges, which may lead to a problem of segmented discrete masks undermining the performance of segmentation. Although self‐attention can be implemented to capture long‐distance dependencies between pixels, it has the disadvantage of computational complexity and the global contexts extracted by self‐attention are still insufficient. To this end, the authors propose the GFRNet, which resorts to the idea of low‐rank matrix factorization by forming global contexts locally to obtain global contexts that are totally different from contexts extracted by self‐attention. The authors effectively integrate the different global contexts extract by self‐attention and low‐rank matrix factorization to extract versatile global contexts. Also, to recover the spatial contexts lost during the matrix factorization process and enhance boundary contexts, the authors propose the Modified Matrix Decomposition module which employ depth‐wise separable convolution and spatial augmentation in the low‐rank matrix factorization process. Comprehensive experiments are performed on four benchmark datasets showing that GFRNet performs better than the relevant CNN and transformer‐based recipes. [ABSTRACT FROM AUTHOR]

In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain multiple edges, loops, and semi-edges. A graph is called simple if it contains no semi-edges, no loops, and no multiple edges. A graph covering projection, also known as a locally bijective homomorphism, is a mapping between vertices and edges of two graphs which preserves incidences and which is a local bijection on the edge-neighborhood of every vertex. This notion stems from topological graph theory, but has also found applications in combinatorics and theoretical computer science. It has been known that for every fixed simple regular graph H of valency greater than 2, deciding if an input graph covers H is NP-complete. Graphs with semi-edges have been considered in this context only recently and only partial results on the complexity of covering such graphs are known so far. In this paper we consider the list version of the problem, called List-H-Cover, where the vertices and edges of the input graph come with lists of admissible targets. Our main result reads that the List-H-Cover problem is NP-complete for every regular graph H of valency greater than 2 which contains at least one semi-simple vertex (i.e., a vertex which is incident with no loops, with no multiple edges and with at most one semi-edge). Using this result we show the NP-co/polytime dichotomy for the computational complexity of List-H-Cover for cubic graphs. [ABSTRACT FROM AUTHOR]