Search

Real-time, accurate, and robust localisation is critical for autonomous vehicles (AVs) to achieve safe, efficient driving, whilst real-time performance is essential for AVs to achieve their current position in time for decision making. To date, no review paper has quantitatively compared the real-time performance between different localisation techniques based on various hardware platforms and programming languages and analysed the relations among localisation methodologies, real-time performance and accuracy. Therefore, this paper discusses state-of-the-art localisation techniques and analyses their localisation performance in AV application. For further analysis, this paper firstly proposes a localisation algorithm operations capability (LAOC)-based equivalent comparison method to compare the relative computational complexity of different localisation techniques; then, it comprehensively discusses the relations among methodologies, computational complexity, and accuracy. Analysis results show that the computational complexity of localisation approaches differs by a maximum of about 〖10〗^7 times, whilst accuracy varies by about 100 times. Vision- and multi-sensor fusion-based localisation techniques have about 2–5 times potential for improving accuracy compared with lidar-based localisation. Lidar- and vision-based localisation can reduce computational complexity by improving image registration method efficiency. Multi-sensor fusionbased localisation can achieve better real-time performance compared with lidar- and vision-based localisation because each standalone sensor does not need to develop a complex algorithm to achieve its best localisation potential. Vehicle-to-everything (V2X) technology can improve positioning robustness. Finally, results show that the fusion technique combined with V2X has considerable potential for achieving a cost-efficient localisation solution for AVs.

We study the algorithmic problem of finding the most “scale-free-like” spanning tree of a connected graph. This problem is motivated by the fundamental problem of genomic epidemiology: given viral genomes sampled from infected individuals, reconstruct the transmission network (“who infected whom”). We use two possible objective functions for this problem and introduce the corresponding algorithmic problems termed m-SF (-scale free) and s-SF Spanning Tree problems. We prove that those problems are APX- and NP-hard, respectively, even in the classes of cubic and bipartite graphs. We propose two integer linear programming (ILP) formulations for the s-SF Spanning Tree problem, and experimentally assess its performance using simulated and experimental data. In particular, we demonstrate that the ILP-based approach allows for accurate reconstruction of transmission histories of several hepatitis C outbreaks.

Mobile robots with complex onboard equipment are investigated in this article. It is shown that their onboard equipment, for providing the required reliability parameters, must have fault-tolerant properties. For designing such equipment it is necessary to have an adequate model of reliability parameters evaluation. The approach, linked to the creation of the model, based on parallel semi-Markov process apparatus, is considered. At the first stage of modeling, the lifetime of the single block in a complex fault-recovery cycle is determined. Dependences for the calculation of time intervals and probabilities of wandering through ordinary semi-Markov processes for a common case are obtained. At the second stage, ordinary processes are included in the parallel one, which simulates the lifetime of the equipment lifetime as a whole. To simplify calculations, a digital model of faults with the use of the procedure of histogram sampling is proposed. It is shown that the number of samples permits to control both the accuracy and the computational complexity of the procedure for calculating the reliability parameters.

The first definition of space complexity for P systems was based on a hypothetical real implementation by means of biochemical materials, and thus it assumes that every single object or membrane requires some constant physical space. This is equivalent to using a unary encoding to represent multiplicities for each object and membrane. A different approach can also be considered, having in mind an implementation of P systems in silico; in this case, the multiplicity of each object in each membrane can be stored using binary numbers, thus reducing the amount of needed space. In this paper, we give a formal definition for this alternative space complexity measure, we define the corresponding complexity classes and we compare such classes both with standard space complexity classes and with complexity classes defined in the framework of P systems considering the original definition of space.

We show that the feasibility of a booking in the European entry-exit gas market can be decided in polynomial time on single-cycle networks that are passive, i.e. do not contain controllable elements. The feasibility of a booking can be characterized by solving polynomially many nonlinear potential-based flow models for computing so-called potential-difference maximizing load flow scenarios. We thus analyze the structure of these models and exploit both the cyclic graph structure as well as specific properties of potential-based flows. This enables us to solve the decision variant of the nonlinear potential-difference maximization by reducing it to a system of polynomials of constant dimension that is independent of the cycle's size. This system of fixed dimension can be handled with tools from real algebraic geometry to derive a polynomial-time algorithm. The characterization in terms of potential-difference maximizing load flow scenarios then leads to a polynomial-time algorithm for deciding the feasibility of a booking. Our theoretical results extend the existing knowledge about the complexity of deciding the feasibility of bookings from trees to single-cycle networks., SCOPUS: ar.j, info:eu-repo/semantics/published

Online sequential extreme learning machine (OS-ELM) has become a popular online learning strategy for single-hidden layer feedforward neural networks, and complex-valued signals are ubiquitous in real applications. In order to cater for complex-valued signals, especially for noncircular signals, in this paper we extend OS-ELM to complex domain, and propose two augmented online sequential complex ELM models by incorporating the conjugates of the network input and the hidden layer respectively. In this way, the proposed models are equipped with the capability to capture the complete second-order statistics of noncircular signals, which results in the enhanced generalization ability. The corresponding regularized models are derived to avoid the possible overfitting problem. By exploiting the algebra structure resulted from the augmented architecture, several approaches to reducing the computational complexity are also proposed. Simulation results validate the efficiency of the proposed algorithms.

The paper discusses adaptive filtering using Least Mean Square (LMS) and Recursive Least Square (RLS) algorithms. An algorithm for adjusting the coefficients of an adaptive digital filter in the Residue Number System and a procedure of developed algorithm applying depending on filter length and signal length are proposed. Mathematical modeling of the considered algorithms is performed. Examples are presented to demonstrate how the proposed technique can help the designer in the adjustment of the filter coefficients without the need for extensive trial-and-error procedures. The analysis of the denoising quality and computational complexity is made. Synthetic and real data (earthquake recording) were used while testing. The proposed algorithm surpasses the existing ones like LMS and RLS, and their modifications in a number of parameters: adaptation (denoising) quality, ease of implementation, execution time. The main difference between the developed algorithm is the sequential adaptation of each coefficient with zero error. In the known algorithms, the entire vector of coefficients is iteratively adapted, with some specified accuracy. The iterations (steps) number is determined by the input signal length for all algorithms.

In this paper we study the question of parallelization of a variant of Branch-and-Bound method for solving of the subset sum problem which is a special case of the Boolean knapsack problem. The following natural approach to the solution of this question is considered. At the first stage one of the processors (control processor) performs some number of algorithm steps of solving a given problem with generating some number of subproblems of the problem. In the second stage the generated subproblems are sent to other processors for solving (one subproblem per processor). Processors solve completely the received subproblems and return their solutions to the control processor which chooses the optimal solution of the initial problem from these solutions. For this approach we define formally a model of parallel computing (frontal parallelization scheme) and the notion of complexity of the frontal scheme. We study the asymptotic behavior of the complexity of the frontal scheme for two special cases of the subset sum problem.

The Minimum Maximum Outdegree Problem (MMO) is to assign a direction to every edge in an input undirected, edge-weighted graph so that the maximum weighted outdegree taken over all vertices becomes as small as possible. In this paper, we introduce a new variant of MMO called the p-Split Minimum Maximum Outdegree Problem (p-Split-MMO) in which one is allowed to perform a sequence of p split operations on the vertices before orienting the edges, for some specified non-negative integer p, and study its computational complexity.

The distributed FxLMS algorithm based on acoustic sensor networks can solve the problem of the increased computational complexity caused by a large-scale active noise control (ANC) system. Firstly, the distributed algorithm is deduced theoretically. In the ANC process based on sensor networks, the iteration of partial weight coefficients is replaced by the real-time communication of weight coefficients among nodes. Then the convergence characteristics of the distributed algorithm in its mean and mean square senses are analyzed and verified with simulation. Finally, the noise reduction effects of different algorithms are compared. The results show that the distributed algorithm, with its computational complexity reduced, can achieve the same noise reduction effects as the centralized ANC system.

11th International Conference on Algorithms and Complexity ( 2019: Rome; Italy ), Hedonic games are a prominent model of coalition formation, in which each agent’s utility only depends on the coalition she resides. The subclass of hedonic games that models the formation of general partnerships [21], where output is shared equally among affiliates, is called hedonic games with common ranking property (HGCRP). Aside from their economic motivation, HGCRP came into prominence since they are guaranteed to have core stable solutions that can be found efficiently [2]. Nonetheless, a core stable solution is not necessarily a socially desirable (Pareto optimal) outcome. We improve upon existing results by proving that every instance of HGCRP has a solution that is both Pareto optimal and core stable. We establish that finding such a solution is, however, - by proving the stronger statement that finding any Pareto optimal solution is. We show that the gap between the total utility of a core stable solution and that of the socially optimal solution (OPT) is bounded by |N|, where N is the set of agents, and that this bound is tight. Our investigations reveal that finding a solution, whose total utility is within a constant factor of that of OPT, is intractable. © 2019, Springer Nature Switzerland AG.

In reaction systems, preimages and nth ancestors are sets of reactants leading to the production of a target set of products in either 1 or n steps, respectively. Many computational problems on preimages and ancestors, such as finding all minimum-cardinality nth ancestors, computing their size or counting them, are intractable. In this paper, we characterize all nth ancestors using a Boolean formula that can be computed in polynomial time. Once simplified, this formula can be exploited to easily solve all preimage and ancestor problems. This allows us to directly relate the difficulty of ancestor problems to the cost of the simplification so that new insights into computational complexity investigations can be achieved. In particular, we focus on two problems: (i) deciding whether a preimage/nth ancestor exists and (ii) finding a preimage/nth ancestor of minimal size. Our approach is constructive, it aims at finding classes of reactions systems for which the ancestor problems can be solved in polynomial time, in exact or approximate way.

P systems with active membranes have been widely used to attack problems in $${\mathbf{NP}}$$ or even in $${{\mathbf{PSPACE }}}$$; in general, an exponential amount of space is generated in polynomial time by dividing existing membranes. Natural questions arise in this framework, concerning the power of P systems when different bounds are considered for the use of the space resource. We consider in this paper two natural bounds: the amount of available physical space (in terms of the number of objects and membranes) and the organization of the membrane structure (in particular, concerning the depth of the membrane structure). We present the main results obtained so far on this subject.

Probabilistic Bipolar Abstract Argumentation Frameworks (prBAFs), combining the possibility of specifying supports between arguments with a probabilistic modeling of the uncertainty, have been recently considered [34, 35] and the complexity of the problem of computing extensions' probabilities has been characterized [22]. In this paper we deal with the problem of computing extensions' probabilities over prBAFs where the probabilistic events that arguments, supports and defeats occur in the real scenario are assumed to be independent probabilistic events (prBAFS of type IND). Specifically an algorithm for efficiently computing extensions' probabilities under the stable and admissible semantics has been devised and its efficiency has been experimentally validated w.r.t. the exhaustive approach, i.e. the approach consisting in the generation of all the possible scenarios, showing that the proposed algorithm outperforms the exhaustive approach.

In view to the unstable navigation risk assessment and make the future navigation risk forecasting, an innovative decision and forecasting approach is put forward in this study. Different from the existing literature, at the current time step, we first deduce an enhanced evidence combination rule to integrate uncertain and conflicting evidences by using weighted basic probabilistic assignment and matrix operation. As a result, a stable decision is effectively achieved no matter what characteristics of the available evidences are. Further, an improved α-β filter is designed with its adaptive coefficients in the novel filtering framework in order to forecast the future navigation risk. What's more, it is an excellent communication between the combined basic probabilistic assignment and the improved α-β filter for the first time. After the deep analysis of the computational complexity, a plenty of numeric simulations and actual experiments are provided to indicate the reliability and efficiency of the proposed approach.

The alternating direction method of multipliers (ADMM) is one of most foundational algorithms for linear constrained composite minimization problems. For different specific problems, variations of ADMM (like linearized ADMM, proximal ADMM) are developed. By using the Bregman distances, lots of ADMMs can be formulated into a uniform mathematical scheme. Although variational inequalities have been well used to study ADMMs, the use for BADMM has still been missing. In this paper, we study the convergence of BADMM by variational inequalities. We present a proof framework for BADMMs. And then, we present very concise convergence proof for the basic BADMM. As applications, we consider several variations of BADMM and obtain corresponding convergence results.

A polar projection-based algorithm is proposed to reduce the computational complexity associated with dimension reduction in unsupervised learning. This algorithm employs $K$ -means clustering. A new distance metric is developed to account for peak consumption in cluster consumer load profiles. It is used to cluster the load profiles according to both total and peak consumption. To accelerate the clustering process, a stochastic-based approach is developed to reduce the search space to find the cluster centers. Numerical results are presented which show a significant reduction in computational complexity using both polar-based and stochastic-based clustering compared to conventional approaches. Further, the estimation error is low.

The aim of this work is to reduce the computational complexity of lossless compression in the spatial domain due to the combined coding (arithmetic and Run-Length Encoding) of a series of bits of bit planes. Known effective compression encoders separately encode the bit planes of the image or transform coefficients, which leads to an increase in computational complexity due to multiple processing of each pixel. The paper proposes the rules for combined coding and combined encoders for bit planes of pixel differences of images with a tunable and constant structure, which have lower computational complexity and the same compression ratio as compared to an arithmetic encoder of bit planes.

This study investigates the task assignment problem where a fleet of dispersed vehicles needs to visit multiple target locations in a time-invariant drift field with obstacles while trying to minimise the vehicles' total travel time. The vehicles have different capabilities, and each kind of vehicles can visit a certain type of the target locations; each target location might require to be visited more than once by different kinds of vehicles. The task assignment problem has been proven to be NP-hard. A path planning algorithm is first designed to minimise the time for a vehicle to travel between two given locations through the drift field while avoiding any obstacle. The path planning algorithm provides the travel cost matrix for the target assignment, and generates routes once the target locations are assigned to the vehicles. Then, a distributed algorithm is proposed to assign the target locations to the vehicles using only local communication. The algorithm guarantees that all the visiting demands of every target will be satisfied within a total travel time that is at worst twice of the optimal when the travel cost matrix is symmetric. Numerical simulations show that the algorithm can lead to solutions close to the optimal.

Here, a simplified algorithm to calculate log-likelihood ratio (LLR) for m-QAM demodulation is proposed. Traditional method calculating LLR for m-QAM demodulation is supposed to do distance computing between any two constellation points so that the high complexity of the hardware implementation is not acceptable. This simplified method is different from the traditional ways that the distance calculation between any two points in a plane can be omitted, indicating that there is an advantage in the amount of computation in this simplified method. Finally, the simplified method is compared with traditional methods from the perspective of complexity and system performance. The simulation results show that the simplified method can greatly reduce the amount of calculation and have little effect on the performance of the system.

Fractionally spaced super-exponential (FSSE) algorithm has the disadvantage of computational complexity since it exploits high-order statistics explicitly. The authors propose a dimension degradation technique for FSSE when it is applied to the equalisation of a sparse channel in accordance with the relationship between the coefficients of the cross fourth-order cumulant (CFOC) in FSSE and the channel impulse response. They implement partial updating on the prominent coefficients of the CFOC with all the small coefficients remaining unchanged. The computational complexity of the modified FSSE reduces significantly with an acceptable performance loss, and its performance is validated via numerical simulations.

In this study, a 2D adaptive beamforming algorithm for sparse array is proposed. Firstly, a signal model based on matrix completion theory for adaptive beamforming in sparse array is established, which is proved to satisfy null space property. Secondly, in order to enhance the performance of reconstructing complete received signal matrix, genetic algorithm is used to optimise the sparse sampling array. Thirdly, the accelerated proximal gradient algorithm is adopted to reconstruct the complete received signal matrix. Finally, the adaptive beamforming weight is provided directly to form beam patterns, which can be obtained as a result of reconstructing complete received signal matrix. The proposed method could improve the utilisation rate of the sparse array elements and reduce the computational complexity in interference suppression. Simulation results show the effectiveness of the method.

We survey a selection of inconsistency measures from the literature and investigate their computational complexity wrt. decision problems related to bounds on the inconsistency value and the functional problem of determining the actual value. Our findings show that those inconsistency measures can be partitioned into four classes related to their complexity. The first three classes contain measures whose complexities are located on the first three levels of the polynomial hierarchy, respectively. The final class is under standard complexity-theoretic assumptions located beyond the polynomial hierarchy. We provide membership results for all the investigated problems and completeness results for most of them. In addition, we undertake a preliminary study on the computational complexity of the measures on fragments of propositional logic.

We study the computational complexity of various problems related to synchronization of weakly acyclic automata, a subclass of widely studied aperiodic automata. We provide upper and lower bounds on the length of a shortest word synchronizing a weakly acyclic automaton or, more generally, a subset of its states, and show that the problem of approximating this length is hard. We investigate the complexity of finding a synchronizing set of states of maximum size. We also show inapproximability of the problem of computing the rank of a subset of states in a binary weakly acyclic automaton and prove that several problems related to recognizing a synchronizing subset of states in such automata are NP-complete., Comment: Extended and corrected version, including arXiv:1608.00889. Conference version was published at CIAA 2017, LNCS vol. 10329, pages 188-200, 2017

Some theories are explored in this research about decision trees which give theoretical support to the applications based on decision trees. The first is that there are many splitting criteria to choose in the tree growing process. The splitting bias that influences the criterion chosen due to missing values and variables with many possible values has been studied. Results show that the Gini index is superior to entropy information as it has less bias regarding influences. The second is that noise variables with more missing values have a better chance to be chosen while informative variables do not. The third is that when there are many noise variables involved in the tree building process, it influences the corresponding computational complexity. Results show that the computational complexity increase is linear to the number of noise variables. So methods that decompose more information from the original data but increase the variable dimension can also be considered in real applications.

Despite being a central concept in cheminformatics, molecular similarity has so far been limited to the simultaneous comparison of only two molecules at a time and using one index, generally the Tanimoto coefficent. In a recent contribution we have not only introduced a complete mathematical framework for extended similarity calculations, (i.e. comparisons of more than two molecules at a time) but defined a series of novel idices. Part 1 is a detailed analysis of the effects of various parameters on the similarity values calculated by the extended formulas. Their features were revealed by sum of ranking differences and ANOVA. Here, in addition to characterizing several important aspects of the newly introduced similarity metrics, we will highlight their applicability and utility in real-life scenarios using datasets with popular molecular fingerprints. Remarkably, for large datasets, the use of extended similarity measures provides an unprecedented speed-up over “traditional” pairwise similarity matrix calculations. We also provide illustrative examples of a more direct algorithm based on the extended Tanimoto similarity to select diverse compound sets, resulting in much higher levels of diversity than traditional approaches. We discuss the inner and outer consistency of our indices, which are key in practical applications, showing whether then-ary and binary indices rank the data in the same way. We demonstrate the use of the newn-ary similarity metrics ont-distributed stochastic neighbor embedding (t-SNE) plots of datasets of varying diversity, or corresponding to ligands of different pharmaceutical targets, which show that our indices provide a better measure of set compactness than standard binary measures. We also present a conceptual example of the applicability of our indices in agglomerative hierarchical algorithms. The Python code for calculating the extended similarity metrics is freely available at:https://github.com/ramirandaq/MultipleComparisons

With precise angle measurement, traditional monopulse techniques for forward-looking imaging can acquire exact angle information of one single target within a radar beam. However, when multiple targets exist in a beam, it is difficult to resolve them. To address this problem, a novel monopulse forward-looking imaging algorithm based on Levenberg–Marquardt (LM) optimisation is proposed. The core idea of this algorithm is to solve maximum likelihood estimation problem based on LM optimisation (ML-LM) to obtain the direction of arrival (DOA) estimation of unresolved targets. First, the echo model of two targets within a forward-looking radar beam is established, then the imaging framework of the proposed algorithm is introduced. Finally, the advantages of ML-LM are illustrated based on a series of evaluation criterion, including angle measurement error for various values of signal-to-noise ratio (SNR), angle interval adaptability and computational efficiency. The simulation results show that two targets within a forward-looking radar beam can be resolved and relocated accurately utilising the proposed algorithm. Meanwhile, the comparison with other algorithms shows it has higher DOA estimation accuracy, less computational complexity and a wider range of angle interval adaptability.

The problem of DOA estimation for sub-array multiple-input multiple-output radar is concerned. Employing compressive sampling concept and the minimum mean-square error (MMSE) technology, the proposed algorithm alternates between updating sample covariance matrix and the MMSE filter bank values until convergence. Simplified array manifolds are considered to decrease the computational complexity. The core idea of the algorithm is to determine the DOA by calculating the spatial distribution of signal power adaptively. Simulation results show that the new algorithm performs well both in a wide SNR range and limited samples, compared with the MUSIC, PIAA-APES, and OGSBI algorithms. The most outstanding advantage of the new algorithm is that it can maintain high estimation accuracy under limited samples without knowing the number of targets.

Image restoration and denoising is an essential preprocessing step for almost every subsequent task in computer vision. Markov Random Fields offer a well-founded, sophisticated approach for this purpose, but unfortunately the associated computation procedures are not sufficiently fast, due to a high-dimensional optimization problem. While the increase of computing power could not solve this runtime issue appropriately, we address it in a mathematical way: we suggest an analytical solution for the optimum of the inference problem, which provides desirable mathematical properties. In practice, our new method accelerates the runtime via reducing the computational complexity of the image restoration task by orders of magnitude, independent from the smoothing intensity. As a result, Markov Random Fields can be considered for modern big data problems in computer vision, especially if numerous images with equal sizes are processed.

Given an undirected graph, a star partition is a partition of the nodes into subsets with at least two nodes so that the subgraph induced by each subset has a spanning star. Star partitions are related to well-known problems concerning domination in graphs and edge covering. We focus on the Constrained Star Partition Problem (CSP) that asks for finding a star partition of given cardinality. The problem is new and presents interesting peculiarities. We explore the relation between the cardinalities of star partitions and domatic bipartitions, showing that there are star partitions of any cardinality between minimum and maximum values, and that a similar but weaker result holds for domatic bipartitions. We study the computational complexity of different versions of star partition and domatic bipartition problems, proving that most of them, in particular CSP, constrained domatic bipartition and balanced domatic bipartition, are NP-complete. We also show that star partition problems are polynomial on trees and, more generally, on bounded treewidth graphs. We introduce an integer linear programming formulation that defines a polytope containing all the star partitions of a graph, showing that its vertices have only integral components for trees, which implies that linear programming can be used to solve weighted star partition problems on trees.

Question-answering systems like Watson beat humans when it comes to processing speed and memory. But what happens if we compensate for this? What are the fundamental differences in power between human and artificial agents in question answering? We explore this issue by defining new computational models for both agents and comparing their computational efficiency in interactive sessions. Concretely, human agents are modeled by means of cognitive automata, augmented with a form of background intelligence which gives the automata the possibility to query a given Turing machine and use the answers from one interaction to the next. On the other hand, artificial question-answering agents are modeled by QA-machines, which are Turing machines that can access a predefined, potentially infinite knowledge base (‘advice’) and have a bounded amount of learning space at their disposal. We show that cognitive automata and QA-machines have exactly the same potential in realizing question-answering sessions, provided the resource bounds in one model are sufficient to match the abilities of the other. In particular, polynomially bounded cognitive automata with background intelligence (i.e. human agents) prove to be equivalent to polynomially bounded QA-machines with logarithmic learning space. It generalizes Pippenger's theorem on the computational power of switching circuits (without background intelligence) to a foundational result for question answering in cognitive science. The framework reveals why QA-machines have a fundamental advantage.

Target localisation using frequency diverse array (FDA) has drawn much attention owing to the additional degree of freedom in the range dimension. However, the Doppler effect was often ignored in previous FDA works because of the stationary target assumption, and in contrast, even stationary target localisation could be of quite a high computational complexity. In this study, a method is proposed that can jointly estimate range, angle, and Doppler for FDA multiple-input-multiple-output radar with low computational complexity. First, Doppler is estimated independently by utilising unstructured maximum likelihood method. Next, traditional two-dimensional (2D) MUSIC is divided into multiple one-dimensional (1D) MUSIC to estimate the angle. Then substituting the estimated angle into the former 2D MUSIC results in a 1D searching over range dimension to get the range estimation. The advantage of the proposed method was verified by simulation results.

We introduce collective decision-making models associated with influence spread under the linear threshold model in social networks. We define the oblivious and the non-oblivious influence models. We also introduce the generalized opinion leader–follower model (gOLF) as an extension of the opinion leader–follower model (OLF) proposed by van den Brink et al. (2011). In our model we allow rules for the final decision different from the simple majority used in OLF. We show that gOLF models are non-oblivious influence models on a two-layered bipartite influence digraph. Together with OLF models, the satisfaction and the power measures were introduced and studied. We analyze the computational complexity of those measures for the decision models introduced in the paper. We show that the problem of computing the satisfaction or the power measure is #P-hard in all the introduced models even when the subjacent social network is a bipartite graph. Complementing this result, we provide two subfamilies of decision models in which both measures can be computed in polynomial time. We show that the collective decision functions are monotone and therefore they define an associated simple game. We relate the satisfaction and the power measures with the Rae index and the Banzhaf value of an associated simple game. This will allow the use of known approximation methods for computing the Banzhaf value, or the Rae index to their practical computation.

This study introduces a two-level strategy for efficient execution of multiple sequence alignment (MSA) of complex heterogeneous sequences. The two levels of the proposed technique are comprised of: designing the discrete firefly algorithm (DFFA) for the formation and implementation of makespan minimisation on parallel machines, followed by performing Ctrie-based caching for pairwise alignment to reduce the load on the data servers for handling multiple queries. The proposed strategy addresses a multi-client problem that aims to acquire the full advantage of the computational power of parallel connected machines. Further, it is shown that the inclusion of Ctrie as caching mechanism successively improves the performance of the system with accretion in several sequences. Performance of proposed DFFA is also compared with discrete versions of four swarm intelligence based algorithms at the criteria of makespan minimisation and the rate of convergence on two kinds of complex and diverse datasets. The work is unique in this sense: it is the first swarm-intelligence-based implementation for the addressed problem; it is so far the first approach for Ctrie based caching of the MSA on the scheduled parallel machines; hybridisation of DFFA with Ctrie for caching the MSA results is also a novel implementation.

We propose an online algorithm for sequential learning in the contextual multiarmed bandit setting. Our approach is to partition the context space and, then, optimally combine all of the possible mappings between the partition regions and the set of bandit arms in a data-driven manner. We show that in our approach, the best mapping is able to approximate the best arm selection policy to any desired degree under mild Lipschitz conditions. Therefore, we design our algorithm based on the optimal adaptive combination and asymptotically achieve the performance of the best mapping as well as the best arm selection policy. This optimality is also guaranteed to hold even in adversarial environments since we do not rely on any statistical assumptions regarding the contexts or the loss of the bandit arms. Moreover, we design an efficient implementation for our algorithm using various hierarchical partitioning structures, such as lexicographical or arbitrary position splitting and binary trees (BTs) (and several other partitioning examples). For instance, in the case of BT partitioning, the computational complexity is only log-linear in the number of regions in the finest partition. In conclusion, we provide significant performance improvements by introducing upper bounds (with respect to the best arm selection policy) that are mathematically proven to vanish in the average loss per round sense at a faster rate compared to the state of the art. Our experimental work extensively covers various scenarios ranging from bandit settings to multiclass classification with real and synthetic data. In these experiments, we show that our algorithm is highly superior to the state-of-the-art techniques while maintaining the introduced mathematical guarantees and a computationally decent scalability. IEEE

Revealed preference theory is a domain within economics that studies rationalizability of behavior by (certain types of) utility functions. Given observed behavior in the form of choice data, testing whether certain conditions are satisfied gives rise to a variety of computational problems that can be analyzed using operations research techniques. In this survey, we provide an overview of these problems, their theoretical complexity, and available algorithms for tackling them. We focus on consumer choice settings, in particular individual choice, collective choice and stochastic choice settings.

The planning and scheduling of container terminal logistics systems (CTLS) are the multi-objective and multiple strong constraints combinatorial optimization challenges under the uncertain environments, and those are provided with high goal orientation, dynamics, context-sensitivity, coupling, timeliness, and complexity. The increasingly sophisticated decision-making for CTLS is one of the most pressing problems for the programming and optimization method available. This paper discusses CTLS in terms of logistics generalized computation complexity based on computational thinking, great principles of computing, and computational lens, which three are abbreviated with 3CTGPL, and makes a definition of container terminal oriented logistics generalized computational complexity (CTO-LGCC) and container terminal logistics generalized computation comprehensive performance perspective (CTL-GCCPP) from the dimensions of time, space, communication, processor, and memory access. Both can analyze, generalize, migrate, translate, localize, modificate, and evaluate the above-complicated problems and lay solid foundations and establish a feedback improvement framework for the computational model and scheduling algorithms of the CTLS, which is an essential complement to the modeling and optimization methodology and solutions to CTLS with computational logistics. Finally, aimed at the logistics service cases for a large-scale container terminal, the simulation is designed and implemented for different scheduling algorithms, and the qualitative and quantitative comprehensive analysis is executed for the concomitant CTO-LGCC that demonstrates and verifies the feasibility and credibility of the CTO-LGCC and CTL-GCCPP from the viewpoint of the practice of container terminal decision-making support on the tactical level.

The Fermat method is considered to be the best for factorization of numbers N=p×q in case of close p and q. Computational complexity of the basic algorithm of the method is determined by the number of check values of X when solving equation Y2=X2‑N, as well as by complexity of the arithmetic operations. To reduce it, it is proposed to consider admissible those of test values X, for which (X2–N)modbb is quadratic residue modulo bb, called basic. Application of basic foundation of module bb makes it possible to decrease the number of check X by the number of times, close to Z=bb/bb*, where bb* is the number of elements of set Т of the roots of equation (Ymodb)2modb=((Xmodb)2–Nmodb)modb, and Z is the acceleration coefficient.It was determined that magnitude Z(N, bb) is affected by the value of residues Nmodp (at p=2, Nmod8 residues are used). The statement of the problem of finding bb with a maximum Z(N, bb) at restrictions for the amount of memory of the computer, where exponents of prime numbers – multipliers bb – are determined, and the method of its solution were proposed.To decrease the number of arithmetic operations with big numbers, it was proposed that instead of them to perform the operations with the values of differences between the nearest values of elements T. Then arithmetic operations of multiplication and addition with big numbers are performed only in rare cases. And if we derive the square root of X2–N only in cases, where the values of (X2–N)modb will be quadratic residues for many foundations of module b, other than bb, the computational complexity of this operation can be neglected.It was established that the proposed modified algorithm of the Fermat method for numbers 21024 ensures a decrease in computational complexity compared to the basic algorithm on average by 107 times, Метод Ферма считается лучшим при факторизации чисел N=p×q в случае близьких p и q. Вычислительная сложность базового алгоритма метода определяется количеством пробных значений Х при решении уравнения Y2=X2‑N, а также сложностью арифметических операций. Для ее снижения предлагается в качестве допустимых рассматривать те из пробных Х, для которых (X2-N)modbb является квадратичным остатком по модулю bb, названного базовым. Применение базового основания модуля bb позволяет уменшить число пробных Х в число раз, близкое к Z=bb/bb*, где bb* – число элементов множества Т корней уравнения (Ymodb)2modb=((Xmodb)2-Nmodb)modb, а Z – коэффициент ускорения.Определено, что на величину Z(N,bb) влияют значения остатков Nmodp (при р=2 используются остатки Nmod8). Предложена постановка задачи поиска bb с максимальным Z(N,bb) при ограничениях на объем памяти ЭВМ, где определяются показатели степеней простых чисел – множителей bb, и способ ее решения.Для уменьшения числа арифметических операций с большими числами предложено вместо таких выполнять операции со значениями разностей между ближайшими значениями элементов Т. Тогда арифметические операции умножения и сложения с большими числами выполняются только в редких случаях. А если квадратный корень из X2-N определять только в случаях, когда значения (X2-N)modb будут квадратичными остатками для многих оснований модуля b, отличных от bb, то вычислительной сложностью этой операции можно пренебречь.Установлено, что тогда предложенный модифицированный алгоритм метода Ферма для чисел 21024 обеспечивает снижение вычислительной сложности по сравнению с базовым алгоритмом в среднем в 107 раз, Метод Ферма вважається кращим при факторизації чисел N=p×q у випадку близьких p і q. Обчислювальна складність базового алгоритму методу визначається кількістю пробних значень Х при вирішенні рівняння Y2=X2‑N, а також складністю арифметичних операцій. Для її зниження запропоновано в якості допустимих розглядати ті з пробних Х, для яких (X2-N)modbb є квадратним залишком по модулю bb, названого базовым. При використанні базової основи модуля bb число пробних Х зменшується в число раз, близьке до Z(N,bb)=bb/bb*, де bb* – число елементів множини Т коренів рівняння (Ymodb)2modb=((Xmodb)2-Nmodb)modb, а Z – коефіцієнт прискорення.Визначено, що на величину Z(N,bb) впливають значения залишків Nmodp (при р=2 використовуються залишки Nmod8). Запропоновано постановку задачі пошуку bb з максимальным Z(N,bb) при обмеженях на обсяг пам’яті ЕОМ, де визначаються показники степенів простих чисел – множників bb, та спосіб її вирішення.Для зменшення числа арифметичних операцій з великими числами попонується замість таких виконувати операції зі значеннями різниць між найближчими значеннями елементів множини Т. Тоді арифметичні операції множення і додавання з великими числами виконуються рідко. А якщо квадратний корінь з X2-N визначати тільки у випадках, коли значення (X2-N)modb будуть квадратними залишками для багатьох різних основ модуля b, то обчислювальною складністю цієї операції можна знехтувати.Встановлено, що тоді запропонований модифікований алгоритм методу Ферма для чисел 21024 забезпечує зниження обчислювальної складності в порівнянні з базовим алгоритмом в середньому в 107 раз

Generalized spatial modulation (GSM) maps its information to the index of the transmit antenna combination, making simultaneous transmission of multiple symbol possible. However, SM outperform GSM scheme in terms of error performance of the same data rate, due to average power effect. Transmit and receive diversity or the combination of both allow huge improvement in mimo systems in terms of error performance. In this paper, we investigate a near optimal low-complexity Euclidean distance antenna selection (LC-EDAS) technique in GSM system, to further improve the performance of the conventional GSM system. The LC-EDAS technique independently search across signal and spatial dimension to eliminate the worse channel prior to transmission. Secondly, we investigate a sub-optimal low-complexity transmit antenna selection (LCTAS) in the GSM system to further reduce the computational complexity (CC) imposed by LC-EDAS. The Monte Carlo simulation results obtained reveals a trade-off between the GSM scheme with LC-EDAS and GSM scheme with sub-optimal transmit antenna selection in terms of error performance and CC. ABSTRAK: Modulasi Spatial Keseluruhan (GSM) menghubung informasi kepada indeks kombinasi antena yang dipancarkan, membuatkan pemancaran keseluruhan simbol dapat dilakukan. Walau bagaimanapun, SM lebih bagus daripada skim GSM pada prestasi kesilapan pada kadar data yang sama, kerana kesan purata kuasa. Kepelbagaian penghantaran dan penerimaan ataupun kombinasi keduanya memberi pembaharuan yang lebih besar dalam sistem mimo pada prestasi kesalahan. Penyelidikan ini akan mengkaji optima terdekat Euclidean kurang rumit, melalui teknik (LC-EDAS) pilihan jarak antenna dalam sistem GSM, bagi menambah prestasi sistem GSM sedia ada. Teknik LC-EDAS secara sendiri mencari signal dan dimensi separa bagi mengurangkan saluran lebih teruk semasa penghantaran. Kedua, kami mengkaji sub-optima proses pemilihan kurang rumit penyebaran antena (LCTAS) dalam sistem GSM bagi mengurangkan kerumitan pengiraan (CC) yang dikenakan oleh LC-EDAS. Keputusan simulasi Monte Carlo yang diperoleh menunjukkan timbangan antara skim GSM dan LC-EDAS dan skim GSM bersama sub-optima proses pemilihan penyebaran antena berdasarkan kesilapan prestasi dan CC.

We consider two variations of graph total domination, namely, k-tuple total domination and total {k}-domination (for a fixed positive integer k). Their related decision problems are both NP-complete even for bipartite graphs. In this work, we study some subclasses of bipartite graphs. We prove the NP-completeness of both problems (for every fixed k) for bipartite planar graphs and we provide an APX-hardness result for the total domination problem for bipartite subcubic graphs. In addition, we introduce a more general variation of total domination (total (r,m)-domination) that allows us to design a specific linear time algorithm for bipartite distance-hereditary graphs. In particular, it returns a minimum weight total {k}-dominating function for bipartite distance-hereditary graphs. Fil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina Fil: Leoni, Valeria Alejandra. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Torres, Pablo Daniel. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Escuela de Ciencias Básicas; Argentina

In this paper, we investigate dynamic resource scheduling (i.e., joint user, subchannel, and power scheduling) for downlink multi-channel non-orthogonal multiple access (MC-NOMA) systems over time-varying fading channels. Specifically, we address the weighted average sum rate maximization problem with quality-of-service (QoS) constraints. In particular, to facilitate fast resource scheduling, we focus on developing a very low-complexity algorithm. To this end, by leveraging Lagrangian duality and the stochastic optimization theory, we first develop an opportunistic MC-NOMA scheduling algorithm whereby the original problem is decomposed into a series of subproblems, one for each time slot. Accordingly, resource scheduling works in an online manner by solving one subproblem per time slot, making it more applicable to practical systems. Then, we further develop a heuristic joint subchannel assignment and power allocation (Joint-SAPA) algorithm with very low computational complexity, called Joint-SAPA-LCC, that solves each subproblem. Finally, through simulation, we show that our Joint-SAPA-LCC algorithm provides good performance comparable to the existing Joint-SAPA algorithms despite requiring much lower computational complexity. We also demonstrate that our opportunistic MC-NOMA scheduling algorithm in which the Joint-SAPA-LCC algorithm is embedded works well while satisfying given QoS requirements., 43 pages, 13 figures

Gaussian processes (GPs) are commonly used as models for functions, time series, and spatial fields, but they are computationally infeasible for large datasets. Focusing on the typical setting of modeling data as a GP plus an additive noise term, we propose a generalization of the Vecchia (J. Roy. Statist. Soc. Ser. B 50 (1988) 297–312) approach as a framework for GP approximations. We show that our general Vecchia approach contains many popular existing GP approximations as special cases, allowing for comparisons among the different methods within a unified framework. Representing the models by directed acyclic graphs, we determine the sparsity of the matrices necessary for inference, which leads to new insights regarding the computational properties. Based on these results, we propose a novel sparse general Vecchia approximation, which ensures computational feasibility for large spatial datasets but can lead to considerable improvements in approximation accuracy over Vecchia’s original approach. We provide several theoretical results and conduct numerical comparisons. We conclude with guidelines for the use of Vecchia approximations in spatial statistics.

Automatic classification of cough data can play a vital role in early detection of Covid-19. Lots of Covid-19 symptoms are somehow related to the human respiratory system, which affect sound production organs. As a result, anomalies in cough sound is expected to be discovered in Covid-19 patients as a sign of infection. This drives the research towards detection of potential Covid-19 cases with inspecting cough sound. While there are several well-performing deep networks, which are capable of classifying sound with a high accuracy, they are not suitable for using in early detection of Covid-19 as they are huge and power/memory hungry. Actually, cough recognition algorithms need to be implemented in hand-held or wearable devices in order to generate early Covid-19 warning without the need to refer individuals to health centers. Therefore, accurate and at the same time lightweight classifiers are needed, in practice. So, there is a need to either compress the complicated models or design light-weight models from the beginning which are suitable for implementation on embedded devices. In this paper, we follow the second approach. We investigate a new lightweight deep learning model to distinguish Covid and Non-Covid cough data. This model not only achieves the state of the art on the well-known and publicly available Virufy dataset, but also is shown to be a good candidate for implementation in low-power devices suitable for hand-held applications.

A computationally efficient method for online joint state inference and dynamical model learning is presented. The dynamical model combines an a priori known, physically derived, state-space model with a radial basis function expansion representing unknown system dynamics and inherits properties from both physical and data-driven modeling. The method uses an extended Kalman filter approach to jointly estimate the state of the system and learn the unknown system dynamics, via the parameters of the basis function expansion. The key contribution is a computational complexity reduction compared to a similar approach with globally supported basis functions. By using compactly supported radial basis functions and an approximate Kalman gain, the computational complexity is considerably reduced and is essentially determined by the support of the basis functions. The approximation works well when the system dynamics exhibit limited correlation between points well separated in the state-space domain. The method is exemplified via two intelligent vehicle applications where it is shown to: (i) have competitive system dynamics estimation performance compared to the globally supported basis function method, and (ii) be real-time applicable to problems with a large-scale state-space., Comment: 13 pages. \copyright 2021 IEEE

To minimise systematic errors in Monte Carlo simulations of charged particles, long range electrostatic interactions have to be calculated accurately and efficiently. Standard approaches, such as Ewald summation or the naive application of the classical Fast Multipole Method, result in a cost per Metropolis-Hastings step which grows in proportion to some positive power of the number of particles $N$ in the system. This prohibitively large cost prevents accurate simulations of systems with a sizeable number of particles. Currently, large systems are often simulated by truncating the Coulomb potential which introduces uncontrollable systematic errors. In this paper we present a new multilevel method which reduces the computational complexity to $\mathcal{O}(\log(N))$ per Metropolis-Hastings step, while maintaining errors which are comparable to direct Ewald summation. We show that compared to related previous work, our approach reduces the overall cost by better balancing time spent in the proposal- and acceptance- stages of each Metropolis-Hastings step. By simulating large systems with up to $N=10^5$ particles we demonstrate that our implementation is competitive with state-of-the-art MC packages and allows the simulation of very large systems of charged particles with accurate electrostatics., Comment: 19 pages, 9 figures, 1 table

Nature-inspired computing is a type of human-designed computing motivated by nature, which is based on the employ of paradigms, mechanisms, and principles underlying natural systems. In this article, a versatile and vigorous bio-inspired branch of natural computing, named membrane computing is discussed. This computing paradigm is aroused by the internal membrane function and the structure of biological cells. We first introduce some basic concepts and formalisms of membrane computing, and then some basic types or variants of P systems (also named membrane systems ) are presented. The state-of-the-art computability theory and a pioneering computational complexity theory are presented with P system frameworks and numerous solutions to hard computational problems (especially NP -complete problems) via P systems with membrane division are reported. Finally, a number of applications and open problems of P systems are briefly described.

The partial transmit sequences (PTS) is regarded as a promising scheme for inhibiting ‎the high peak-to-average power ratio (PAPR) problem in the orthogonal frequency division ‎multiplexing (OFDM) systems. The PTS scheme relies on partitioning the ‎data sequence into subsets and weighting these subsets by a group of the phase rotation ‎factors. Although the PTS can efficiently reduce the high PAPR value, a great ‎computational complexity (CC) level restricts the utilization of the PTS scheme in practical ‎applications. In PTS, there are three common types of segmentation schemes; ‎interleaving (IL-PTS), pseudo-random (PR-PTS), and adjacent (Ad-PTS) schemes. This ‎paper presents a new algorithm named hybrid pseudo-random and interleaving cosine wave shape ‎‎(H-PRC-PTS) by combining the PR-PTS scheme and the symmetrical ‎interleaving cosine wave shape (S-IL-C-PTS) scheme which was proposed in our previous ‎work. The results indicate that the suggested algorithms can ‎diminish the PAPR value like the PR-PTS scheme, whereas the CC level is reduced significantly.

© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., Many resource allocation problems in the cloud can be described as a basic Virtual Network Embedding Problem (VNEP): the problem of finding a mapping of a request graph (describing a workload) onto a substrate graph (describing the physical infrastructure). Applications range from mapping testbeds, over the embedding of batch-processing workloads to the embedding of service function chains and come with different mapping restrictions for nodes and edges. The restrictions studied most often are node and edge capacities, node mapping and edge routing policies, and latency restrictions. While the VNEP has been studied intensively, complexity results are only known for specific models and this paper provides a first comprehensive study of the computational complexity of the VNEP by systematically analyzing its hardness for any combination of the above stated node and edge mapping restrictions. For all studied variants the NPcompleteness of their respective decision problems is shown. Furthermore, NP-completeness results for finding approximate embeddings, which may, e.g., violate capacity constraints by certain factors, are derived. Lastly, it is also shown that all these results pertain when restricting the request graphs to planar and degree-bounded graphs. While theoretic in nature, our results have severe practical implications. Firstly, any optimization variant of the VNEP is NP-hard and cannot be approximated for any of the studied restrictions, unless P=NP holds. Secondly, we uncover structural hardness properties: the VNEP is NP-hard and inapproximable even if, e.g., only node placement and edge routing restrictions are considered.

The problem of matching a query string to a directed graph, whose vertices are labeled by strings, has application in different fields, from data mining to computational biology. Several variants of the problem have been considered, depending on the fact that the match is exact or approximate and, in this latter case, which edit operations are considered and where are allowed. In this paper we present results on the complexity of the approximate matching problem, where edit operations are symbol substitutions and are allowed only on the graph labels or both on the graph labels and the query string. We introduce a variant of the problem that asks whether there exists a path in a graph that represents a query string with any number of edit operations and we show that is is NP-complete, even when labels have length one and in the case the alphabet is binary. Moreover, when it is parameterized by the length of the input string and graph labels have length one, we show that the problem is fixed-parameter tractable and it is unlikely to admit a polynomial kernel. The NP-completeness of this problem leads to the inapproximability (within any factor) of the approximate matching when edit operations are allowed only on the graph labels. Moreover, we show that the variants of approximate string matching to graph we consider are not fixed-parameter tractable, when the parameter is the number of edit operations, even for graphs that have distance one from a DAG. The reduction for this latter result allows us to prove the inapproximability of the variant where edit operations can be applied both on the query string and on graph labels., Comment: Extended version of a paper accepted to LATA 2020

P systems with active membranes are a variant of P systems where membranes play an active role during the computation, for example by dividing existing membranes in order to create new ones. In this way, an exponential number of membranes can be obtained in polynomial time, and then used in parallel to attack computationally hard problems. Many interesting questions arise concerning the trade-off between time and space needed to solve various classes of computational problems by means of such membrane systems. In this paper we overview the main results presented in the literature concerning this subject.