Search

In dial-a-ride systems involving autonomous vehicles circulating along a circuit, a fleet of vehicles must serve clients who request rides between stations of the circuit such that the total number of pickup and drop-off operations is minimized. In this paper, we focus on a unitary variant where each client requests a single place in the vehicles and all the clients must be served within a single tour of the circuit. Such unitary variant induces a combinatorial optimization problem for which we introduce a nontrivial special case that is polynomially solvable when the capacity of each vehicle is at most 2 but it is NP-Hard otherwise. We also study the polytope associated with the solutions to this problem. We introduce new families of valid inequalities and give necessary and sufficient conditions under which they are facet-defining. Based on these inequalities, we devise an efficient branch-and-cut algorithm that outperforms the state-of-the-art commercial solvers.

This paper proposes a long-horizon direct model predictive control (MPC) with reference tracking for medium-voltage (MV) drives that achieves favorable steady-state and transient behavior. However, as MPC is a model-based method, it is susceptible to parameter mismatches and variations of the machine. Moreover, even though a long prediction horizon significantly improves the steady-state behavior of the drive, it significantly increases the computational complexity of the direct MPC problem, rendering its real-time implementation a challenging—if not impossible—task. Motivated by these shortcomings of long-horizon direct MPC, this paper also aims to address them by enhancing the robustness of the developed control strategy, while keeping its computational complexity modest. To achieve the former, a prediction model suitable for MV drive systems is adopted that facilitates the effective estimation of the total leakage inductance of the machine. For the latter, the objective function of the MPC problem is formulated such that, even though the drive behavior is computed over a long prediction interval, only a few changes in the candidate switch positions are considered. The effectiveness of the proposed modeling, control, and estimation approaches is validated with hardware-in-the-loop (HIL) tests for an MV drive consisting of a three-level neutral point clamped (NPC) inverter and an induction machine (IM). acceptedVersion

The integration of non-terrestrial networks into the 5G ecosystem is mainly driven by the possibility of provisioning service in remote areas. In this context, the advent of flying base stations at the low Earth orbit (LEO) will enable anywhere and anytime connectivity. To materialize this vision, it is of utmost importance to improve radio protocols with the aim of allowing direct satellite access. Bearing this aspect in mind, we present a new random access signal, which is based on the filter bank multicarrier (FBMC) waveform, and a computationally efficient detection scheme. The proposed solution outperforms the standardized access scheme based on single-carrier frequency division multiplexing (SC-FDM), by reducing out-of-band (OOB) emissions and reducing the missed detection probability in presence of very high carrier frequency offset (CFO), which is inherent to LEO satellite systems. The improvement is related to the fine frequency resolution of the detector and the use of pulse shaping techniques. Interestingly, the FBMC-based random access signal achieves a high level of commonality with 5G new radio, as the preamble generation method and the time-frequency allocation pattern can be kept unchanged. Concerning the practical implementation aspects, the complexity of the detector is similar in both SC-FDM and FBMC. This paper is part of the R+D+i project (PID2020-115323RB-C31) funded by MCIN/AEI/ 10.13039/501100011033. This work is supported by the grant from Spanish Ministry of Economic Affairs and Digital Transformation and the European union - NextGenerationEU (UNICO-5G I+D/AROMA3D-Space (TSI-063000-2021-70))

In this study, two multi-step iterative techniques of fifth order convergence are explored to solve nonlinear equations. The techniques are designed with the prime objective of keeping the computational cost as low as possible. To claim this objective, the efficiency indices are determined and compared with the efficiencies of the existing techniques of same order. The outcome of comparison analysis is remarkable from the view of high computational efficiency of new methods. Performance and stability are illustrated by executing the numerical tests on some nonlinear problems of diverse nature. The entire analysis significantly favors the new techniques compared to their existing counterparts, especially for the case of large dimensional systems.

This letter proposes a learning aided gradient descent (LAGD) algorithm to solve the weighted sum rate (WSR) maximization problem for multiple-input single-output (MISO) beamforming. The proposed LAGD algorithm directly optimizes the transmit precoder through implicit gradient descent based iterations, at each of which the optimization strategy is determined by a neural network, and thus, is dynamic and adaptive. At each instance of the problem, this network is initialized randomly, and updated throughout the iterative solution process. Therefore, the LAGD algorithm can be implemented at any signal-to-noise ratio (SNR) and for arbitrary antenna/user numbers, does not require labelled data or training prior to deployment. Numerical results show that the LAGD algorithm can outperform of the well-known WMMSE algorithm as well as other learning-based solutions with a modest computational complexity. Our code is available at https://github.com/XiaGroup/LAGD .

P systems with active membranes are a variant of P systems where membranes can be created by division of existing membranes, thus creating an exponential amount of resources in a polynomial number of steps. Time and space complexity classes for active membrane systems have been introduced, to characterize classes of problems that can be solved by different membrane systems making use of different resources. In particular, space complexity classes introduced initially considered a hypothetical real implementation by means of biochemical materials, assuming that every single object or membrane requires some constant physical space (corresponding to unary notation). A different approach considered implementation of P systems in silico, allowing to store the multiplicity of each object in each membrane using binary numbers. In both cases, the elements contributing to the definition of the space required by a system (namely, the total number of membranes, the total number of objects, the types of different membranes, and the types of different objects) was considered as a whole. In this paper, we consider a different definition for space complexity classes in the framework of P systems, where each of the previous elements is considered independently. We review the principal results related to the solution of different computationally hard problems presented in the literature, highlighting the requirement of every single resource in each solution. A discussion concerning possible alternative solutions requiring different resources is presented.

Parametric timed automata (PTA) have been introduced by Alur, Henzinger, and Vardi as an extension of timed automata in which clocks can be compared against parameters. The reachability problem asks for the existence of an assignment of the parameters to the non-negative integers such that reachability holds in the underlying timed automaton. The reachability problem for PTA is long known to be undecidable, already over three parametric clocks. A few years ago, Bundala and Ouaknine proved that for PTA over two parametric clocks and one parameter the reachability problem is decidable and also showed a lower bound for the complexity class PSPACE^NEXP. Our main result is that the reachability problem for parametric timed automata over two parametric clocks and one parameter is EXPSPACE-complete. For the EXPSPACE lower bound we make use of deep results from complexity theory, namely a serializability characterization of EXPSPACE (in turn based on Barrington’s Theorem) and a logspace translation of numbers in Chinese Remainder Representation to binary representation due to Chiu, Davida, and Litow. It is shown that with small PTA over two parametric clocks and one parameter one can simulate serializability computations. For the EXPSPACE upper bound, we first give a careful exponential time reduction from PTA over two parametric clocks and one parameter to a (slight subclass of) parametric one-counter automata over one parameter based on a minor adjustment of a construction due to Bundala and Ouaknine. For solving the reachability problem for parametric one-counter automata with one parameter, we provide a series of techniques to partition a fictitious run into several carefully chosen subruns that allow us to prove that it is sufficient to consider a parameter value of exponential magnitude only. This allows us to show a doubly-exponential upper bound on the value of the only parameter of a PTA over two parametric clocks and one parameter. We hope that extensions of our techniques lead to finally establishing decidability of the long-standing open problem of reachability in parametric timed automata with two parametric clocks (and arbitrarily many parameters) and, if decidability holds, determining its precise computational complexity., LIPIcs, Vol. 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), pages 36:1-36:18

The main goal of the thesis is to compare the distinguishing power of known combinatorial and algebraic graph invariants. Using the language of refinement operators (introduced in [32]) we derive known results relating the Weisfeiler-Leman algorithms and the invertible map tests. The former are a well known family of polynomial time algorithms parametrised by some natural number, each defining an equivalence on graphs which over-approximates graph isomorphism. The latter, introduced in [30], are parametrised by a natural number and a set of prime numbers. By generalising the concept of coherent algebras to an arbitrary field, we show that the invertible map tests can be viewed as a representation theoretic generalisation of the Weisfeiler-Leman algorithms. We also show that the equivalences defined by each invertible map test over the set of all prime numbers can be decided in polynomial time. This motivates an open question which could lead to interesting insights into the nature and computational complexity of graph isomorphism, as well as the descriptive complexity of finite graphs. We also use refinement operators to bound the expressive power of an infinitary logic with solvability quantifiers so as to study the relative power of the invertible map tests and known proof systems with algebraic rules; namely, bounded degree polynomial calculus, monomial calculus and Nullstellensatz calculus. These are well studied and have been used in the context of graph isomorphism in [14] and [39]. Our results generalise some of the work in the latter two papers and contribute to a deeper understanding of the apparently weaker Nullstellensatz calculus. More precisely, we show that the distinguishing power of Nullstellensatz calculus is essentially the same as that of monomial calculus. Furthermore, in the case of fields of characteristic 0, we show that Nullstellensatz calculus can simulate polynomial calculus in the case of the graph isomorphism problem; hence, combining this with a results by Grohe et al. [39], it follows that over characteristic 0, all three proof systems have similar distinguishing power to the Weisfeiler-Leman algorithms. Building on recent results by Brachter and Schweitzer [16] we look at the behaviour of the Weisfeiler-Leman algorithms on finite groups. Whilst hinting at potential conditions required to construct families of 2-nilpotent groups with high Weisfeiler-Leman dimension, we also show that the class of 2-nilpotent groups generated by trees has low Weisfeiler-Leman dimension. This naturally leads to the question as to whether classes of graphs with low Weisfeiler-Leman dimension generate classes of 2-nilpotent groups with low Weisfeiler-Leman dimension. Lastly, we show that there is a first-order definable reduction from group isomorphism to the isomorphism problem of Latin square graphs of Cayley tables of groups, and vice-versa. The existence of such a bi-interpretation implies that the Weisfeiler-Leman dimensions of finite groups and Latin square graphs of their Cayley tables have a similar asymptotic behaviour.

In this paper we show that if G is a primitive subgroup of Sn that is not large base, then any irredundant base for G has size at most 5 log n. This is the first logarithmic bound on the size of an irredundant base for such groups, and is best possible up to a multiplicative constant. As a corollary, the relational complexity of G is at most 5 log n+1, and the maximal size of a minimal base and the height are both at most 5 log n. Furthermore, we deduce that a base for G of size at most 5 log n can be computed in polynomial time. Publisher PDF

Common cyclic prefix-orthogonal frequency-division multiplexing (CCP-OFDM) groups multiple OFDM symbols and uses one CP to protect them in slow time-variant channels. However, due to this particular design of CCP-OFDM systems, complex time-domain estimation algorithms are used to estimate and equalize the channel, such as maximum likelihood (ML) estimators. In this letter, we propose a novel CCP-OFDM transceiver design enabling low-complexity frequency-domain channel estimation and equalization. Simulations under frequency selective channels have validated the effectiveness of the proposed scheme in terms of computational complexity, normalized mean squared error (NMSE), and bit error rate (BER).

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.

The subject of research in the article are algorithms for fast calculation of autoregression coefficients in digital spectral analysis and estimation of the number of arithmetic operations required for their implementation. The aim of the article – comparative analysis of the speed of different algorithms for calculating the coefficients of autoregression as part of the algorithms of spectral analysis, including analysis of the complexity of their microcontroller implementation. Tasks to be solved: selection of spectral analysis methods suitable for diagnostics of technological equipment, analysis of methods for calculating autoregression coefficients and derivation of relations for estimating software complexity of algorithms and calculation of numerical estimates of addition and multiplication for some algorithms, adaptation of developed methods and estimates to microcontrollers. spectrum Applied methods: algorithm theory, Fourier transform, natural series, microcontroller programming. The results obtained: it is shown that spectral estimation methods based on Yul-Walker equations, which require the calculation of autoaggression coefficients, combine sufficient resolution and resistance to interference with acceptable implementation complexity. Estimates of the number of additions and multiplications for the Levinson, Durbin, and Trench algorithms are obtained, and their comparative analysis is performed. The calculation times for microcontroller arithmetic with fixed and floating points were count upon. Conclusions: When constructing spectrum analyzers for the diagnosis of technological equipment, it is advisable to use the Yul-Walker method. A comparison of Levinson, Durbin, and Trench algorithms for calculating autoregression coefficients showed that the Trench method requires a minimum number of additions, and the Durbin method requires a minimum number of multiplications. At microcontroller realization of spectrum analyzers, it is necessary to consider features of the arithmetic used by the controller. The Trench method is the fastest in the case of floating-point arithmetic and small-scale modeling. In other cases, Durbin's method is more effective., Предметом исследования в статье являются алгоритмы быстрого вычисления коэффициентов авторегрессии при цифровом спектральном анализе и оценки числа арифметических операций, необходимых для их выполнения. Цель статьи - сравнительный анализ быстродействия различных алгоритмов вычисления коэффициентов авторегрессии как составной части алгоритмов спектрального анализа, в том числе анализ сложности их микроконтроллерной реализации. Решаемые задачи: выделение методов спектрального анализа, пригодных для диагностики технологического оборудования, вывод соотношений для оценивания программной сложности алгоритмов и расчет числовых оценок вычислительной сложности, адаптация разработанных методов и оценок к микроконтроллерной реализации анализаторов спектра. Применяемые методы: теория алгоритмов, преобразование Фурье, линейная алгебра, натуральные ряды, программирование микроконтроллеров. Полученные результаты: показано, что метод спектрального оценивания на основе уравнений Юла-Уолкера, требующих вычисления коэффициентов авторегрессии, сочетает достаточную разрешающую способность и помехоустойчивость с приемлемой сложностью реализации. Получены оценки числа сложений и умножений для алгоритмов Левинсона, Дурбина и Тренча и выполнен их сравнительный анализ. Рассчитаны времена вычисления для микроконтроллерной арифметики с фиксированной и плавающей запятой. Выводы: сравнение алгоритмов Левинсона, Дурбина и Тренча для вычисления коэффициентов авторегресси показало, что метод Тренча требует минимального количества сложений, а метод Дурбина – минимального количества умножений. При микроконтроллерной реализации анализаторов спектра следует учитывать особенности используемой контроллером арифметики. Метод Тренча является наиболее быстродействующим в случае применения арифметики с плавающей точкой и небольшого порядка модели. В остальных случаях более эффективен метод Дурбина., Предметом дослідження у статті є алгоритми швидкого обчислення коефіцієнтів авторегресії при цифровому спектральному аналізі та оцінки кількості арифметичних операцій, необхідних для їх реалізації. Мета статті – порівняльний аналіз швидкодії різних алгоритмів обчислення коефіцієнтів авторегресії як складової частини алгоритмів спектрального аналізу, у тому числі аналіз складності їхньої мікроконтролерної реалізації. Завдання, що вирішуються: виділення методів спектрального аналізу, придатних для діагностики технологічного обладнання, аналіз методів обчислення коефіцієнтів авторегресії та виведення співвідношень для оцінювання програмної складності алгоритмів та розрахунок числових оцінок числа додавань та множень для деяких алгоритмів, адаптація розроблених методів та оцінок до мікроконтролерної реалізації аналізаторів спектру Застосовувані методи: теорія алгоритмів, перетворення Фур’є, натуральні ряди, програмування мікроконтролерів. Отримані результати: показано, що методи спектрального оцінювання на основі рівнянь Юла-Уолкера, що вимагають обчислення коефіцієнтів авторегресії, поєднує достатню роздільну здатність і стійкість до перешкод з прийнятною складністю реалізації. Отримано оцінки числа додавань та множень для алгоритмів Левінсона, Дурбіна та Тренча, виконано їх порівняльний аналіз. Розраховані часи обчислення для мікроконтролерної арифметики з фіксованою та плаваючою точкою. Висновки: При побудові аналізаторів спектра для діагностики технологічного обладнання доцільно застосовувати метод Юла-Уолкера. Порівняння алгоритмів Левінсона, Дурбіна та Тренча для обчислення коефіцієнтів авторегресії показало, що метод Тренча потребує мінімальної кількості додавань, а метод Дурбіна – мінімальної кількості множень. При мікроконтролерній реалізації аналізаторів спектра слід враховувати особливості використовуваної контролером арифметики. Метод Тренча є найбільш швидкодіючим у разі застосування арифметики з плаваючою точкою та невеликого порядку моделі. В інших випадках ефективніший метод Дурбіна.

Kramers-Kronig (KK) receiver shows strong feasibility since the phase can be extracted from the detected intensity through the Hilbert transform (HT). To reduce the complexity and make the HT more suitable for the practical KK system, the HT can be approximated as the finite impulse response (FIR) filter, i.e. the HT-FIR filter. However, the finite Fourier series expansion of the HT-FIR filter suffers from oscillations around the discontinuities and further results in an unsatisfactory in-band flatness, which is the so-called Gibbs phenomenon. In the experiment and the simulation, we found that the performance of the KK system using the HT-FIR filter is strongly impaired due to the Gibbs phenomenon, by the roll-off factor of the shaping filter, frequency gap between the direct-current (DC) component and one edge of the signal spectrum, carrier-to-signal power ratio (CSPR), tap number of the HT-FIR filter, and the digital upsampling rate. We have systematically investigated the practical KK phase retrieval performance and the computational complexity considering the Gibbs phenomenon due to the adoption of the HT-FIR filter, rather than the HT used in the previous works without the Gibbs phenomenon. We conclude that there is an optimal upsampling rate when the HT-FIR filter is used, and the optimal upsampling rate is closely related to the five aspects mentioned above. We have carried out a transmission experiment using a 112-Gbit/s 16-QAM system over 1920-km with a Raman fiber amplifier to investigate the limit transmission performance of the practical KK receiver. The experimental results show that by using the 9-tap HT-FIR filter with a digital upsampling rate of 84-GHz (3-sps), the signals can be transmitted the same distance as the HT, up to 1440-km with a bit error ratio (BER) below the 20% soft-decision forward error correction threshold.

This paper offers a comprehensive review of selection methods used in the generational genetic algorithms.Firstly, a brief description of the following selection methods is presented: fitness proportionate selection methods including roulette-wheel selection (RWS) and its modifications, stochastic remainder selection with replacement (SRSWR), remainder stochastic independent selection (RSIS), and stochastic universal selection (SUS); ranking selection methods including linear and nonlinear rankings; tournament selection methods including deterministic and stochastic tournaments as well as tournaments with and without replacement; elitist and truncation selection methods; fitness uniform selection scheme (FUSS).Second, basic theoretical statements on selection method properties are given. Particularly, the selection noise, selection pressure, growth rate, reproduction rate, and computational complexity are considered. To illustrate selection method properties, numerous runs of genetic algorithms using the only selection method and no other genetic operator are conducted, and numerical characteristics of analyzed properties are computed. Specifically, to estimate the selection pressure, the takeover time and selection intensity are computed; to estimate the growth rate, the ratio of best individual copies in two consecutive populations is computed; to estimate the selection noise, the algorithm convergence speed is analyzed based on experiments carried out on a specific fitness function assigning the same fitness value to all individuals.Third, the effect of selection methods on the population fitness distribution is investigated. To do this, there are conducted genetic algorithm runs starting with a binomially distributed initial population. It is shown that most selection methods keep the distribution close to the original one providing an increased mean value of the distribution, while others (such as disruptive RWS, exponential ranking, truncation, and FUSS) change the distribution significantly. The obtained results are illustrated with the help of tables and histograms., Розглянуто методи відбору, що використовуються в генетичних алгоритмах із генераційним типом репродукції. Наведено основні теоретичні відомості про такі властивості методів відбору: шум, тиск, швидкість росту, швидкість репродукції, обчислювальна складність. Проведено порівняльний аналіз методів відбору за зазначеними властивостями. Охарактеризовано та проілюстровано зміни в розподілі коефіцієнта пристосованості особин популяції після застосування різних методів відбору.

We consider the interpolation problem associated with the back-projection (BP), fast BP (FBP), and fast factorized BP (FFBP) algorithms exploited in synthetic aperture radar (SAR). The 2-D interpolation required by FBP and FFBP must be properly performed to mitigate the effect of the truncation error and to achieve accurate results, and can be effectively performed by adopting 2-D nonuniform fast Fourier transform (NUFFT) routines.

This paper is on a brief interpretation of class P and NP in infinite Hamming cube consisting all the instances of any language in P or NP as well as all the instances of a Turing machine’s tape per configuration. It is shown that P and NP are more comparable when defined in Hamming space; while, this results P = NP.

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.

In this work, we propose a method to enhance the convergence of the Born series. The Born series is widely used in scattering theory, but its convergence is only guaranteed under certain restrictive conditions which limit the cases where this formulation can be applied. The proposed method, based on modifying the singularities of the resolvent operator by a change of variables, accelerates the convergence of the series or even achieves convergence in otherwise divergent cases. Due to its low computational cost and ease of implementation, the method preserves the advantages of the Born series while it extends its range of application. It can also be applied to a variety of methods relying on the same mathematical principles as the Born series. Numerical examples are provided to show that a significant improvement can be achieved with simple techniques and with a limited knowledge about the operator spectrum. This work was partly funded by the Ministerio de Ciencia e Innovacion (MICINN) under projects TEC2016-78028-C3-1-P, MDM2016-0600, TEC2017-83343-C4-2-R, TEC2017-84817-C2-2-R, PID 2019-107885GB-C31 and Catalan Research Group 2017 SGR 219; and by Secretary of Universities and Research of the Ministry of Business and Knowledge of the Generalitat of Catalonia and European Social Fund under scholarship 2019 FI B00788.

This work investigates the effectiveness of deep neural networks within the realm of battery charging. This is done by introducing an innovative control methodology that not only ensures safety and optimizes the charging current, but also substantially reduces the computational complexity with respect to traditional model-based approaches. In addition to their high computational costs, model-based approaches are also hindered by their need to accurately know the model parameters and the internal states of the battery, which are typically unmeasurable in a realistic scenario. In this regard, the deep learning-based methodology described in this work was been applied for the first time to the best of the authors’ knowledge, to scenarios where the battery’s internal states cannot be measured and an estimate of the battery’s parameters is unavailable. The reported results from the statistical validation of such a methodology underline the efficacy of this approach in approximating the optimal charging policy.

The management of the supply chain for enterprise-wide operations generally consists of strategic, tactical, and operational decision stages dependent on one another and affecting various time scales. Their integration usually leads to multiscale models that are computationally intractable. The design and operation of energy hubs faces similar challenges. Renewable energies are challenging to model due to the high level of intermittency and uncertainty. The multiscale (i.e., planning and scheduling) energy hub systems that incorporate renewable energy resources become more challenging to model due to an integration of the multiscale and high level of intermittency associated with renewable energy. In this work, a mixed-integer programming (MILP) superstructure is proposed for clustering shape-based time series data featuring multiple attributes using a multi-objective optimization approach. Additionally, a data-driven statistical method is used to represent the intermittent behavior of uncertain renewable energy data. According to these methods, the design and operation of an energy hub with hydrogen storage was reformulated following a two-stage stochastic modeling technique. The main outcomes of this study are formulating a stochastic energy hub optimization model which comprehensively considers the design and operation planning, energy storage system, and uncertainties of DRERs, and proposing an efficient size reduction approach for large-sized multiple attributes demand data. The case study results show that normal clustering is closer to the optimal case (full scale model) compared with sequence clustering. In addition, there is an improvement in the objective function value using the stochastic approach instead of the deterministic. The present clustering algorithm features many unique characteristics that gives it advantages over other clustering approach and the straightforward statistical approach used to represent intermittent energy, and it can be easily incorporated into various distributed energy systems.

The locality of a graph problem is the smallest distance $T$ such that each node can choose its own part of the solution based on its radius-$T$ neighborhood. In many settings, a graph problem can be solved efficiently with a distributed or parallel algorithm if and only if it has a small locality. In this work we seek to automate the study of solvability and locality: given the description of a graph problem $\Pi$, we would like to determine if $\Pi$ is solvable and what is the asymptotic locality of $\Pi$ as a function of the size of the graph. Put otherwise, we seek to automatically synthesize efficient distributed and parallel algorithms for solving $\Pi$. We focus on locally checkable graph problems; these are problems in which a solution is globally feasible if it looks feasible in all constant-radius neighborhoods. Prior work on such problems has brought primarily bad news: questions related to locality are undecidable in general, and even if we focus on the case of labeled paths and cycles, determining locality is $\mathsf{PSPACE}$-hard (Balliu et al., PODC 2019). We complement prior negative results with efficient algorithms for the cases of unlabeled paths and cycles and, as an extension, for rooted trees. We introduce a new automata-theoretic perspective for studying locally checkable graph problems. We represent a locally checkable problem $\Pi$ as a nondeterministic finite automaton $\mathcal{M}$ over a unary alphabet. We identify polynomial-time-computable properties of the automaton $\mathcal{M}$ that near-completely capture the solvability and locality of $\Pi$ in cycles and paths, with the exception of one specific case that is $\mbox{co-$\mathsf{NP}$}$-complete.

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.

With the rapid growth of satellite communication demand and the continuous development of high-throughput satellite systems, the satellite resource allocation problem—also called the dynamic resources management (DRM) problem—has become increasingly complex in recent years. The use of metaheuristic algorithms to obtain acceptable optimal solutions has become a hot topic in research and has the potential to be explored further. In particular, the treatment of invalid solutions is the key to algorithm performance. At present, the unused bandwidth allocation (UBA) method is commonly used to address the bandwidth constraint in the DRM problem. However, this method reduces the algorithm’s flexibility in the solution space, diminishes the quality of the optimized solution, and increases the computational complexity. In this paper, we propose a bandwidth constraint handling approach based on the non-dominated beam coding (NDBC) method, which can eliminate the bandwidth overlap constraint in the algorithm’s population evolution and achieve complete bandwidth flexibility in order to increase the quality of the optimal solution while decreasing the computational complexity. We develop a generic application architecture for metaheuristic algorithms using the NDBC method and successfully apply it to four typical algorithms. The results indicate that NDBC can enhance the quality of the optimized solution by 9–33% while simultaneously reducing computational complexity by 9–21%.

This paper presents a novel design of Flag sequences whose ambiguity functions (AFs) are featured by the peak-curtain property. Such a property can be exploited for efficient identification of the AF peak by first searching the curtain, thus leading to low-complexity delay-Doppler estimation. Motivated by the high AF sidelobes of the existing Flag sequences, we propose to minimize the customized weighted integrated sidelobe level (CWISL) with the aid of an Accelerated Partially Majorization-Minimization Algorithm (APMMA). Numerical results demon-strate that our optimized Flag sequences have lower CWISL and peak sidelobe level (PSL) in the delay-Doppler zone of interest. Agency for Science, Technology and Research (A*STAR) Submitted/Accepted version The work of L. Meng and Y. L. Guan was supported by A*STAR under its RIE2020 Advanced Manufacturing and Engineering (AME) Industry Alignment Fund - Pre Positioning (IAF-PP) under Grant No. A19D6a0053.

Spiking neural membrane systems are models of computation inspired by the natural functioning of the brain using the concepts of neurons and synapses, and represent a way of building computational systems of a biological inspiration. A variant of such a model, allowing to create new neurons and synapses during the computation, has been considered in the literature to attack computationally hard problems, like problems in the class NP. In this work, we investigate the computational properties of this variant, by proposing three solutions to computationally hard problems, by models with different features, and comparing them with those present in the literature. In particular, we first propose a nondeterministic solution for the NP-complete problem 3-SAT, by a model using dynamic organization of synapses. Then, we propose a deterministic solution for the same problem, by a model using neuron division and dissolution rules. Finally, we show that dissolution rules are not strictly necessary (by accepting a certain amount of slowdown in computing time), and that also problems beyond the class NP can be solved by systems with neuron division alone.

In this paper, we consider a subset selection problem in a spatial field where we seek to find a set of k locations whose observations provide the best estimate of the field value at a finite set of prediction locations. The measurements can be taken at any location in the continuous field, and the covariance between the field values at different points is given by the widely used squared exponential covariance function. One approach for observation selection is to perform a grid discretization of the space and obtain an approximate solution using the greedy algorithm. The solution quality improves with a finer grid resolution but at the cost of increased computation. We propose a method to reduce the computational complexity, or conversely to increase solution quality, of the greedy algorithm by considering a search space consisting only of prediction locations and centroids of cliques formed by the prediction locations. We demonstrate the effectiveness of our proposed approach in simulation, both in terms of solution quality and runtime., Comment: Accepted for publication at European Control Conference, 2022

—An accurate epileptic seizure detector using intracranial electroencephalography (iEEG) recordings, suitable for low power wearable/implantable applications, is presented. Eleven time-domain features with low hardware complexity are employed in the feature pool of the seizure detector. A novel two-step feature ranking algorithm based on maximum discrimination minimum redundancy (MDMR) is proposed to identify the most discriminating features in a patient-specific manner during a training phase. Subsequently, the top-ranked features are extracted in a two-stage energy-efficient architecture in which the second stage is activated by a controller to avoid unnecessary energy consumption imposed by multiple feature extraction during the long period of non-seizure states. The effective number of features which are continuously extracted is reduced in this work.Moreover, a patient-specific data reduction technique which selects the most informative and discriminating iEEG channels is also proposed.The presented channel selection technique reaches 68% data reduction on average for the tested patients and reduces the computational complexity. The proposed algorithm is implemented on Cyclone V FPGA of Terasic DE10-standard board. It is tested on twelve patients with shortterm and long-term seizures from the Bern Inselspital dataset. The FPGA implementation results reveal an excellent sensitivity of 100% for all patients and remarkable specificity and detection delay improvement compared to the state-of-the-art. The average dynamic power consumption is 0.49mWwhich is in the acceptable range for low-power wearable/implantable applications. In addition, a new figure-of-merit (FoM_SD) is defined to consider the major parameters of the seizure detectors. The outstanding FoM_SD of this work is 0.464 which outperforms the state-of-the-art. Files and How to use them: In TBCAS 2022 folder, Two Matlab .m files are included. These files are related to training phase and test phase signal processing of patient ID3 from SWEC-ETHZ dataset.To run the code correctely, the file ID3_train must be run prior to runnig the ID3_test file. In addition, the VHDL codes consists of feature extraction, and controller hardware codes. All features are extracted in a two-stage architecture managed by the controller unit. The features are selected according to the trainnig phase signal processing codes in Matlab files. &nbsp

Major research efforts have been recently made to develop resource orchestration solutions to flexibly link edge nodes with centralised cloud resources so as to maximise the efficiency with which such a continuum of resources can be accessed by users. In this context, we consider the case of Big Data analytics in which total task completion time reductions can be achieved by routing tasks initially to edge servers and subsequently to cloud resources. We demonstrate that the task complexity of the computational jobs, the Wide Area Network (WAN) speed and the potential overload of edge servers (as reflected by CPU workloads) are crucial for achieving total task completion time reductions by offloading from edge to cloud resources. The edge-cloud orchestrators are situated in the edge nodes and, therefore, require continuous access to the parameters of WAN speeds (and their fluctuations), edge server CPU workload and the task complexities in Big Data analytics requirements to make accurate edge-to-cloud offloading decisions. With favourable values for these three parameters, large reductions in completion times can result from transfer of large-scale data from edge nodes to cloud resources, which can reduce the completion times by up to 97% and meet client deadlines for computational tasks with responsive and agile solutions.

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.

The common feature for a nontrivial hard problem is the existence of nontrivial topological structures, non-planarity graphs, nonlocalities, or long-range spin entanglements in a model system with randomness. For instance, the Boolean satisfiability (K-SAT) problems for K ≥ 3 MSATK≥3 are nontrivial, due to the existence of non-planarity graphs, nonlocalities, and the randomness. In this work, the relation between a spin-glass three-dimensional (3D) Ising model MSGI3D with the lattice size N = mnl and the K-SAT problems is investigated in detail. With the Clifford algebra representation, it is easy to reveal the existence of the long-range entanglements between Ising spins in the spin-glass 3D Ising lattice. The internal factors in the transfer matrices of the spin-glass 3D Ising model lead to the nontrivial topological structures and the nonlocalities. At first, we prove that the absolute minimum core (AMC) model MAMC3D exists in the spin-glass 3D Ising model, which is defined as a spin-glass 2D Ising model interacting with its nearest neighboring plane. Any algorithms, which use any approximations and/or break the long-range spin entanglements of the AMC model, cannot result in the exact solution of the spin-glass 3D Ising model. Second, we prove that the dual transformation between the spin-glass 3D Ising model and the spin-glass 3D Z2 lattice gauge model shows that it can be mapped to a K-SAT problem for K ≥ 4 also in the consideration of random interactions and frustrations. Third, we prove that the AMC model is equivalent to the K-SAT problem for K = 3. Because the lower bound of the computational complexity of the spin-glass 3D Ising model CLMSGI3D is the computational complexity by brute force search of the AMC model CUMAMC3D, the lower bound of the computational complexity of the K-SAT problem for K ≥ 4 CLMSATK≥4 is the computational complexity by brute force search of the K-SAT problem for K = 3 CUMSATK=3. Namely, CLMSATK≥4=CLMSGI3D≥CUMAMC3D=CUMSATK=3. All of them are in subexponential and superpolynomial. Therefore, the computational complexity of the K-SAT problem for K ≥ 4 cannot be reduced to that of the K-SAT problem for K < 3.

The goals and targets included in the 2030 Agenda compiled by the United Nations want to stimulate action in areas of critical importance for humanity and the Earth. These goals and targets regard everyone on Earth from both the health and economic and social perspectives. Reaching these goals means to deal with Complex Systems. Therefore, Complexity Science is undoubtedly valuable. However, it needs to extend its scope and focus on some specific objectives. This article proposes a development of Complexity Science that will bring benefits for achieving the United Nations’ aims. It presents a list of the features shared by all the Complex Systems involved in the 2030 Agenda. It shows the reasons why there are certain limitations in the prediction of Complex Systems’ behaviors. It highlights that such limitations raise ethical issues whenever new technologies interfere with the dynamics of Complex Systems, such as human beings and the environment. Finally, new methodological approaches and promising research lines to face Complexity Challenges included in the 2030 Agenda are put forward.

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

This paper deals with decomposition of complete graphs on $n$ vertices into circulant graphs with reduced degree $r< n-1$ . They are denoted as $C_{n}(a_{1}, a_{2}, {\dots }, a_{m})$ , where $a_{1}$ to $a_{m}$ are generators. Mathematical labeling for such bigger (higher order and huge size) and complex (strictly regular with so many triangles) graphs is very difficult. That is why after decomposition, an edge irregular $k$ -labeling for these subgraphs is computed with the help of algorithmic approach. Results of $k$ are computed by implementing this iterative algorithm in computer. Using the values of $k$ , an upper bound for edge irregularity strength is suggested for $C_{n}(a_{1}, a_{2}, {\dots }, a_{m})$ that is ${\vert E\vert }/{2}\log _{2} \vert V\vert $ .

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.

Fuzzy Logic Controller (FLC) as speed controller is preferred in many AC machine drives, due to its ability to handle model non-linearity, speed variations and parameters change. Additionally, Self-Tuning FLC (ST-FLC) is a modified FLC controller to overcome the issues associated with a fixed parameter FLC and to avoid performance degradation of the machine drive. It can update the FLC parameters in accordance to any variation, changes or disturbances that may occur to the drive system. However, FLC system requires huge computation capacity which increases the computational burden of the overall machine drive system and may result in poor performance. This research proposed a simple ST-FLC mechanism to tune the main FLC speed controller. Three different rule-size of FLC (9, 25, and 49) rules are implemented with ST-FLC mechanism based Induction Motor (IM) drive. Performance comparison of the three different rule-size based ST-FLC is conducted based on simulation and experimental analysis. In addition, a computational effort is technically analyzed and compared for the three different rule-size. In the experiment, ST-FLC with less number of rules (9-rules) shows superior performance, lower sampling and lower computational efforts compared to ST-FLC with higher rule-size (25, 49) rules.

Non-orthogonal multiple access (NOMA) has been recognized as an essential technology for beyond fifth-generation (beyond-5G) wireless networks to increase connectivity, spectral efficiency, cell-edge throughput, and user fairness. In this paper, we propose two subcarrier-user assignment algorithms (SUAAs) for the downlink NOMA system to enhance the spectral efficiency, the fairness, the data rate of weak users, and the outage probability. The assignment order of the first proposed SUAA is based on the worst subcarrier first (WSF) to avoid selecting a user with the worst channel gain with any subcarrier and called (WSF-SUAA). On the other hand, the second proposed SUAA is based on spectral efficiency maximization (SEM) and called (SEM-SUAA), but requires exhaustive search. The assignment process of both algorithms is based on making the channel gain of the selected paired users per subcarrier as high as possible to increase the data rate of each user. Besides, the assignment process of strong users for all subcarriers is performed before the assignment process of weak users to increase the total system sum-rate. It is exposed throughout the simulation that the two proposed SUAAs can attain significant improvement in the total spectral efficiency, weak user data rate, outage probability, and user fairness compared to the existing algorithms. While the performances of the two proposed SUAAs are convergent, the computational complexity of WSF-SUAA is significantly lower than that of SEM-SUAA and slightly higher than that of the existing 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.

Assessing where and how information is stored in biological networks (such as neuronal and genetic networks) is a central task both in neuroscience and in molecular genetics, but most available tools focus on the network’s structure as opposed to its function. Here, we introduce a new information-theoretic tool—information fragmentation analysis—that, given full phenotypic data, allows us to localize information in complex networks, determine how fragmented (across multiple nodes of the network) the information is, and assess the level of encryption of that information. Using information fragmentation matrices we can also create information flow graphs that illustrate how information propagates through these networks. We illustrate the use of this tool by analyzing how artificial brains that evolved in silico solve particular tasks, and show how information fragmentation analysis provides deeper insights into how these brains process information and “think”. The measures of information fragmentation and encryption that result from our methods also quantify complexity of information processing in these networks and how this processing complexity differs between primary exposure to sensory data (early in the lifetime) and later routine processing.

Significance We show that under widely believed complexity theoretic hypotheses, one cannot expect to find provably correct and efficient algorithms for predicting epidemic dynamics on general networks. These results hold even under idealized problem formulations, where all the model parameters are known and are insensitive to changes in environment. Further, they hold even for a small time horizon with just one random parameter, namely, the transmission probability. Thus, computational complexity poses an inherent challenge to effective and efficient epidemic forecasting in network models. Our results do not rule out heuristics that work well in practice or algorithms that provide provable guarantees for restricted networks. Rather, they suggest that algorithms working across a range of inputs should exploit properties of problem instances., The ongoing COVID-19 pandemic underscores the importance of developing reliable forecasts that would allow decision makers to devise appropriate response strategies. Despite much recent research on the topic, epidemic forecasting remains poorly understood. Researchers have attributed the difficulty of forecasting contagion dynamics to a multitude of factors, including complex behavioral responses, uncertainty in data, the stochastic nature of the underlying process, and the high sensitivity of the disease parameters to changes in the environment. We offer a rigorous explanation of the difficulty of short-term forecasting on networked populations using ideas from computational complexity. Specifically, we show that several forecasting problems (e.g., the probability that at least a given number of people will get infected at a given time and the probability that the number of infections will reach a peak at a given time) are computationally intractable. For instance, efficient solvability of such problems would imply that the number of satisfying assignments of an arbitrary Boolean formula in conjunctive normal form can be computed efficiently, violating a widely believed hypothesis in computational complexity. This intractability result holds even under the ideal situation, where all the disease parameters are known and are assumed to be insensitive to changes in the environment. From a computational complexity viewpoint, our results, which show that contagion dynamics become unpredictable for both macroscopic and individual properties, bring out some fundamental difficulties of predicting disease parameters. On the positive side, we develop efficient algorithms or approximation algorithms for restricted versions of forecasting problems.

In this paper, we describe a hierarchy of program transformers, capable of performing fusion to eliminate intermediate data structures, in which the transformer at each level of the hierarchy builds on top of those at lower levels. The program transformer at level 1 of the hierarchy corresponds to positive supercompilation, and that at level 2 corresponds to distillation. We give a number of examples of the application of our transformers at different levels in the hierarchy and look at the speedups that are obtained. We determine the maximum speedups that can be obtained at each level, and prove that the transformers at each level terminate.

The integration of non-terrestrial networks into the 5G ecosystem is mainly driven by the possibility of provisioning service in remote areas. In this context, the advent of flying base stations at the low Earth orbit (LEO) will enable anywhere and anytime connectivity. To materialize this vision, it is of utmost importance to improve radio protocols with the aim of allowing direct satellite access. Bearing this aspect in mind, we present a new random access signal, which is based on the filter bank multicarrier (FBMC) waveform, and a computationally efficient detection scheme. The proposed solution outperforms the standardized access scheme based on single-carrier frequency division multiplexing (SC-FDM), by reducing out-of-band (OOB) emissions and reducing the missed detection probability in presence of very high carrier frequency offset (CFO), which is inherent to LEO satellite systems. The improvement is related to the fine frequency resolution of the detector and the use of pulse shaping techniques. Interestingly, the FBMC-based random access signal achieves a high level of commonality with 5G new radio, as the preamble generation method and the time-frequency allocation pattern can be kept unchanged. Concerning the practical implementation aspects, the complexity of the detector is similar in both SC-FDM and FBMC. IEEE

The 2-domination number gamma(2)(G) of a graph G is the minimum cardinality of a set D subset of V (G) for which every vertex outside D is adjacent to at least two vertices in D. Clearly, gamma(2)(G) cannot be smaller than the domination number gamma(G). We consider a large class of graphs and characterize those members which satisfy gamma(2) = gamma. For the general case, we prove that it is NP-hard to decide whether gamma(2) = gamma holds. We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily., Slovenian Research Agency [N1-0108], Research of Csilla Bujt ' as was partially supported by the Slovenian Research Agency under the project N1-0108.

Cyber-Physical Systems (CPS) are used to perform complex, safety-critical missions autonomously. Examples include applications of autonomous vehicles and drones. Given the complexity of these systems, CPS must be able to adapt to possible changes during mission execution, such as regulatory updates or changes in mission objectives. This capability is informally referred to as resilience. We formalize the intuitive notion of resilience as a formal verification property using timed multiset rewriting. An important innovation in our formalization is the distinction between rules that are under the control of the CPS and those that are not. We also study the computational complexity of resilience problems. Although undecidable in general, we show that these problems are PSPACE-complete for a class of bounded systems, more precisely, balanced systems where the rules do not affect the number of facts of the configurations and where facts are of bounded size.

We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in $\mathbf{DelayP}$, for which a formal way of comparison was not possible to this day., Comment: 20 pages, 1 figure

This research focuses on the k-center problem and its applications. Different methods for solving this problem are analyzed. The implementations of an exact algorithm and of an approximate algorithm are presented. The source code and the computation complexity of these algorithms are presented and analyzed. The multitasking mode of the operating system is taken into account considering the execution time of the algorithms. The results show that the approximate algorithm finds solutions that are not worse than two times optimal. In some case these solutions are very close to the optimal solutions, but this is true only for graphs with a smaller number of nodes. As the number of nodes in the graph increases (respectively the number of edges increases), the approximate solutions deviate from the optimal ones, but remain acceptable. These results give reason to conclude that for graphs with a small number of nodes the approximate algorithm finds comparable solutions with those founds by the exact algorithm. © 2022 Institute of Advanced Engineering and Science. All rights reserved.

Постановка задачи: Применение различных алгоритмов решения задачи коммивояжера, таких как метод ветвей и границ, генетический алгоритм, алгоритм имитации отжига, жадный алгоритм, зачастую не учитывают реальных возможностей вычислительных машин, способных их реализовать. Повышенные требования предъявляются к бортовым вычислителям беспилотных летательных аппаратов (БЛА), осуществляющих специфические задачи в условиях неблагоприятной внешней среды. Увеличивать возможности бортового вычислителя до варианта электронной вычислительной машины, реализующего функции расчета на «земле», не представляется, в настоящее время, возможным из-за ограничений, связанных с массово-габаритными показателями аппарата. Поэтому вопросы синтеза алгоритмов оптимизации с целью удовлетворения требований к аппаратно-программной части беспилотного летательного аппарата военного назначения остаются самостоятельной проблемой. Целью работы является построение алгоритма решения задачи коммивояжера, основанного на совместном использовании муравьиного и генетического алгоритмов, что позволит реализовать вычислительные процедуры алгоритмов решения различных специальных задач, требующие от вычислителя больших объемов памяти и высокой скорости обработки информации. Используемые методы: для решения задачи поиска целевых объектов противника в условиях неблагоприятных действий внешней среды наиболее подходящими по своей вычислительной сложности, оптимальному времени на поиск, и отвечающими требованиям бортовых вычислителей, являются муравьиный и генетический алгоритмы. В качестве критериев оптимизации решаемой задачи в работе предлагается использовать максимизацию количества точек в маршруте и минимизацию времени их облета БЛА. Новизна: элементами новизны представленной работы являются с одной стороны, применение комплексного критерия, включающего в себя минимизацию времени решения задачи и максимизацию количества точек облета маршрута, а с другой стороны, построение процедуры итерактивного исключения «подциклов», входящих в структуру алгоритма, что позволяет разрешить NP-сложность решения такого типа задач за полиномиальное время. Результат: использование представленного алгоритма поиска субоптимального решения задачи коммивояжера с учетом приоритета целей, неравнозначности точек облета и, возникающих на пути препятствий, в условиях дестабилизирующих воздействий противника позволило обеспечить требуемые вычислительные возможности бортового вычислителя БЛА при максимальном покрытии зоны облета. Предложена процедура сужения полного множества оптимальных маршрутов облета неравноценных точек до парето-оптимального множества. Разработанные программы на языке C++, и построенная информационно-вычислительная система с визуальным интерфейсом позволили провести оценку сложности алгоритмов. Комплексирование методов имитации отжига, муравьиного алгоритма с генетическим алгоритмом для решения поставленной задачи позволило снизить время работы алгоритма на 13% по сравнению с методом ветвей и границ. Практическая значимость: выполненные в работе исследования показали, что предложенный алгоритм может быть реализован в виде программы, записанной в память современного бортового спецвычислителя БЛА, что позволит осуществлять автономный полет группой БЛА на больших территориях и охватывать более 66 точек облета., Purpose. The use of various algorithms for solving the traveling salesman problem, such as the method of branches and boundaries, genetic algorithm, simulated annealing algorithm, greedy algorithm, often do not take into account the real capabilities of computers capable of implementing them. Increased requirements are imposed on on-board computers of unmanned aerial vehicles (UAVs) performing specific tasks in an unfavorable external environment. It is not currently possible to increase the capabilities of the on-board computer to a computer variant that implements the calculation functions on the "Ground" due to the limitations associated with the mass-dimensional characteristics of the device. Therefore, the issues of synthesis of existing optimization algorithms in order to meet the requirements for the hardware and software of an unmanned aerial vehicle remain an independent problem. The aim of the work is to build an algorithm for solving the traveling salesman problem based on the combined use of ant and genetic algorithms, which will allow implementing computational procedures for algorithms for solving various special tasks that require large amounts of memory and high information processing speed from the computer. Methods: to solve the problem of searching for enemy targets in the conditions of unfavorable actions of the external environment, the most suitable in terms of computational complexity, optimal search time and meeting the requirements of on-board computers are ant and genetic algorithms. As criteria for optimizing the problem being solved, it is proposed to use maximizing the number of points in the route and minimizing the time of their flight by an unmanned aerial vehicle. Novelty. The novelty elements of the presented work are, on the one hand, the application of a complex criterion, which includes minimizing the time of solving the problem and maximizing the number of points of flight of the route, and on the other hand, the construction of a procedure for iterative elimination of "subcycles" included in the structure of the algorithm, which allows to solve the NP-complexity of solving this type of problems in polynomial time. Results. The use of the presented algorithm for searching for a suboptimal solution to the traveling salesman problem, taking into account the priority of targets, the disparity of flyover points and obstacles arising on the way, under the influence of electronic warfare and enemy air defense, made it possible to provide the required computing capabilities of the onboard computer with maximum coverage of the flyover zone. A procedure is proposed for narrowing the complete set of optimal flyby routes of unequal points to a Pareto-optimal set. The developed program codes in the C++ language, and the built information and computing system. Practical relevance. the research carried out in the work has shown that such an algorithm can be implemented in the form of a program recorded in the memory card of an onboard modern special calculator of an unmanned aerial vehicle, which will allow autonomous flight by a group of UAVs over large territories and cover more than 66 points of flight.

Multiphysics or multiscale problems naturally involve coupling at interfaces which are manifolds of lower dimensions. The block-diagonal preconditioning of the related saddle-point systems is among the most efficient approaches for numerically solving large-scale problems in this class. At the operator level, the interface blocks of the preconditioners are fractional Laplacians. At the discrete level, we propose to replace the inverse of the fractional Laplacian with its best uniform rational approximation (BURA). The goal of the paper is to develop a unified framework for analysis of the new class of preconditioned iterative methods. As a final result, we prove that the proposed preconditioners have optimal computational complexity O(N), where N is the number of unknowns (degrees of freedom) of the coupled discrete problem. The main theoretical contribution is the condition number estimates of the BURA-based preconditioners. It is important to note that the obtained estimates are completely analogous for both positive and negative fractional powers. At the end, the analysis of the behavior of the relative condition numbers is aimed at characterizing the practical requirements for minimal BURA orders for the considered Darcy–Stokes and 3D–1D examples of coupled problems.