Submit to Topical Collection Review for Algorithms

Journal Browser

Feature Paper in Algorithms and Complexity Theory

Collection Editors
Collection Information
Keywords
Published Papers

A topical collection in Algorithms (ISSN 1999-4893). This collection belongs to the section "Analysis of Algorithms and Complexity Theory".

Viewed by 24894

Share This Topical Collection

Editor

Prof. Dr. Vangelis Th. Paschos

E-Mail Website
Collection Editor

Université Paris-Dauphine, PSL Research University, CNRS, UMR 7243 LAMSADE, 75016 Paris, France
Interests: complexity theory; worst-case complexity of exact algorithms for NP-hard problems; approximation of NP-hard optimization problems; polynomial approximability; moderately exponential; subexponential and parameterized approximation; algorithmics in dynamic environments
Special Issues, Collections and Topics in MDPI journals

Topical Collection Information

Dear Colleagues,

This Topical Collection “Feature Papers in Analysis of Algorithms and Complexity Theory”, aims to collect high-quality research articles and review articles in the fields of complexity theory, polynomial approximation algorithms for NP-hard problems, exact algorithms for NP-hard problems, and exponential approximation algorithms for polynomial aproximation-hard problems.

Since the aim of this Topical Collection is to illustrate, through selected works, frontier research in complexity and approximation theory, we encourage researchers to contribute papers reflecting the latest progress in their research. Topics include, without being limited to:

Theory of algorithms;
Sorting and searching algorithms;
Parameterized complexity;
Polynomial, moderately exponential, parameterized approximation of NP-hard problems.

Prof. Dr. Vangelis Th. Paschos
Collection Editor

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the collection website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

Theory of algorithms;
Sorting and searching algorithms;
Parameterized complexity;
Polynomial, moderately exponential, parameterized approximation of NP-hard problems;
Automata theory and formal languages;
Computational geometry;
Quantum algorithms;

Published Papers (13 papers)

Download All Papers

2023

Jump to: 2022

25 pages, 477 KiB

Open AccessArticle

Mind the

\tilde{O}

: Asymptotically Better, but Still Impractical, Quantum Distributed Algorithms

by Phillip Kerger, David E. Bernal Neira, Zoe Gonzalez Izquierdo and Eleanor G. Rieffel

Algorithms 2023, 16(7), 332; https://0-doi-org.brum.beds.ac.uk/10.3390/a16070332 - 11 Jul 2023

Cited by 2 | Viewed by 1240

Abstract

We present two algorithms in the quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability: one for producing an approximately optimal Steiner tree, and one for producing an exact directed minimum spanning tree, each of which uses [...] Read more.

\tilde{O} (n^{1 / 4})

rounds of communication and

\tilde{O} (n^{9 / 4})

messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms as well as related classical algorithms, otherwise obscured by

\tilde{O}

notation, revealing that advances are needed to render both the quantum and classical algorithms practical. Full article

23 pages, 8262 KiB

Open AccessArticle

Temporal Multimodal Data-Processing Algorithms Based on Algebraic System of Aggregates

by Andreas Pester, Yevgeniya Sulema, Ivan Dychka and Olga Sulema

Algorithms 2023, 16(4), 186; https://0-doi-org.brum.beds.ac.uk/10.3390/a16040186 - 29 Mar 2023

Viewed by 1441

Abstract

In many tasks related to an object’s observation or real-time monitoring, the gathering of temporal multimodal data is required. Such data sets are semantically connected as they reflect different aspects of the same object. However, data sets of different modalities are usually stored and processed independently. This paper presents an approach based on the application of the Algebraic System of Aggregates (ASA) operations that enable the creation of an object’s complex representation, referred to as multi-image (MI). The representation of temporal multimodal data sets as the object’s MI yields simple data-processing procedures as it provides a solid semantic connection between data describing different features of the same object, process, or phenomenon. In terms of software development, the MI is a complex data structure used for data processing with ASA operations. This paper provides a detailed presentation of this concept. Full article

► Show Figures

Figure 1

30 pages, 11833 KiB

Open AccessArticle

Integral Backstepping Control Algorithm for a Quadrotor Positioning Flight Task: A Design Issue Discussion

by Yang-Rui Li, Chih-Chia Chen and Chao-Chung Peng

Algorithms 2023, 16(2), 122; https://0-doi-org.brum.beds.ac.uk/10.3390/a16020122 - 16 Feb 2023

Cited by 2 | Viewed by 1974

Abstract

For quadrotor control applications, it is necessary to rely on attitude angle changes to indirectly achieve the position trajectory tracking purpose. Several existing literature studies omit the non-negligible attitude transients in the position controller design for this kind of cascade system. The result leads to the position tracking performance not being as good as expected. In fact, the transient behavior of the attitude tracking response cannot be ignored. Therefore, the closed-loop stability of the attitude loop as well as the position tracking should be considered simultaneously. In this study, the flight controller design of the position and attitude control loops is presented based on an integral backstepping control algorithm. This control algorithm relies on the derivatives of the associated virtual control laws for implementation. Examining existing literature, the derivatives of the virtual control law are realized approximated by numerical differentiations. Nevertheless, in practical scenarios, the numerical differentiations will cause the chattering phenomenon of control signals in the presence of unavoidable measurement noise. The noise-induced control signals may further cause damage to the actuators or even diverge the system response. To address this issue, the analytic form for the derivative of the virtual control law is derived. The time derivative virtual control law is analyzed and split into the disturbance-independent compensable and disturbance-dependent non-compensable terms. By utilizing the compensable term, the control chattering due to the differentiation of the noise can be avoided significantly. The simulation results reveal that the proposed control algorithm has a better position tracking performance than the traditional dual-loop control scheme. Meanwhile, a relatively smooth control signal can be obtained for a realistic control algorithm realization. Simulations are provided to illustrate the position tracking issue of a quadrotor and to demonstrate the effectiveness of the proposed compromised control scheme. Full article

► Show Figures

Figure 1

16 pages, 4127 KiB

Open AccessArticle

CUDA and OpenMp Implementation of Boolean Matrix Product with Applications in Visual SLAM

by Amir Zarringhalam, Saeed Shiry Ghidary, Ali Mohades and Seyed-Ali Sadegh-Zadeh

Algorithms 2023, 16(2), 74; https://0-doi-org.brum.beds.ac.uk/10.3390/a16020074 - 29 Jan 2023

Viewed by 1418

Abstract

In this paper, the concept of ultrametric structure is intertwined with the SLAM procedure. A set of pre-existing transformations has been used to create a new simultaneous localization and mapping (SLAM) algorithm. We have developed two new parallel algorithms that implement the time-consuming Boolean transformations of the space dissimilarity matrix. The resulting matrix is an important input to the vector quantization (VQ) step in SLAM processes. These algorithms, written in Compute Unified Device Architecture (CUDA) and Open Multi-Processing (OpenMP) pseudo-codes, make the Boolean transformation computationally feasible on a real-world-size dataset. We expect our newly introduced SLAM algorithm, ultrametric Fast Appearance Based Mapping (FABMAP), to outperform regular FABMAP2 since ultrametric spaces are more clusterable than regular Euclidean spaces. Another scope of the presented research is the development of a novel measure of ultrametricity, along with creation of Ultrametric-PAM clustering algorithm. Since current measures have computational time complexity order,

O (n^{3})

a new measure with lower time complexity,

O (n^{2})

, has a potential significance. Full article

► Show Figures

Figure 1

14 pages, 1460 KiB

Open AccessArticle

Fuzzy Algorithmic Modeling of Economics and Innovation Process Dynamics Based on Preliminary Component Allocation by Singular Spectrum Analysis Method

by Alexey F. Rogachev, Alexey B. Simonov, Natalia V. Ketko and Natalia N. Skiter

Algorithms 2023, 16(1), 39; https://0-doi-org.brum.beds.ac.uk/10.3390/a16010039 - 08 Jan 2023

Cited by 1 | Viewed by 1529

Abstract

In this article, the authors propose an algorithmic approach to building a model of the dynamics of economic and, in particular, innovation processes. The approach under consideration is based on a complex algorithm that includes (1) decomposition of the time series into components using singular spectrum analysis; (2) recognition of the optimal component model based on fuzzy rules, and (3) creation of statistical models of individual components with their combination. It is shown that this approach corresponds to the high uncertainty characteristic of the tasks of the dynamics of innovation processes. The proposed algorithm makes it possible to create effective models that can be used both for analysis and for predicting the future states of the processes under study. The advantage of this algorithm is the possibility to expand the base of rules and components used for modeling. This is an important condition for improving the algorithm and its applicability for solving a wide range of problems. Full article

► Show Figures

Figure 1

2022

Jump to: 2023

19 pages, 6372 KiB

Open AccessArticle

On Deep-Fake Stock Prices and Why Investor Behavior Might Not Matter

by Călin Vâlsan, Elena Druică and Eric Eisenstat

Algorithms 2022, 15(12), 475; https://0-doi-org.brum.beds.ac.uk/10.3390/a15120475 - 15 Dec 2022

Viewed by 1664

Abstract

We propose an agent-based model of financial markets with only one asset. Thirty-two agents follow very simple rules inspired by Wolfram’s Rule 110. They engage in buying, selling, and/or holding. Each agent is endowed with a starting balance sheet marked-to-market in each iteration. The simulation allows for margin calls for both buying and selling. During each iteration, the number of buy, hold, and sell positions is aggregated into a market price with the help of a simple, linear formula. The formula generates a price depending on the number of buy and sell positions. Various results are obtained by altering the pricing formula, the trading algorithm, and the initial conditions. When applying commonly used statistical tools, we find processes that are essentially indistinguishable from the price of real assets. They even display bubbles and crashes, just like real market data. Our model is remarkable because it can apparently generate a process of equivalent complexity to that of a real asset price, but it starts from a handful of initial conditions and a small number of very simple linear algorithms in which randomness plays no part. We contend our results have far-reaching implications for the debate around investor behavior and the regulation of financial markets. Full article

► Show Figures

Figure 1

12 pages, 311 KiB

Open AccessArticle

A Multi-Dimensional Matrix Product—A Natural Tool for Parameterized Graph Algorithms

by Mirosław Kowaluk and Andrzej Lingas

Algorithms 2022, 15(12), 448; https://0-doi-org.brum.beds.ac.uk/10.3390/a15120448 - 28 Nov 2022

Cited by 1 | Viewed by 1247

Abstract

We introduce the concept of a k-dimensional matrix product D of k matrices

A_{1}, \dots, A_{k}

of sizes

n_{1} \times n, \dots, n_{k} \times n,

respectively, where [...] Read more.

We introduce the concept of a k-dimensional matrix product D of k matrices

A_{1}, \dots, A_{k}

of sizes

n_{1} \times n, \dots, n_{k} \times n,

respectively, where

D [i_{1}, \dots, i_{k}]

is equal to

\sum_{ℓ = 1}^{n} A_{1} [i_{1}, ℓ] \times \dots \times A_{k} [i_{k}, ℓ]

. We provide upper bounds on the time complexity of computing the product and solving related problems of computing witnesses and maximum witnesses of the Boolean version of the product in terms of the time complexity of rectangular matrix multiplication. The multi-dimensional matrix product framework is useful in the design of parameterized graph algorithms. First, we apply our results on the multi-dimensional matrix product to the fundamental problem of detecting/counting copies of a fixed pattern graph in a host graph. The recent progress on this problem has not included complete pattern graphs, i.e., cliques (and their complements, i.e., edge-free pattern graphs, in the induced setting). The fastest algorithms for the aforementioned patterns are based on a reduction to triangle detection/counting. We provide an alternative simple method of detection/counting copies of fixed size cliques based on the multi-dimensional matrix product. It is at least as time efficient as the triangle method in cases of

K_{4}

and

K_{5}

. Next, we show an immediate reduction of the k-dominating set problem to the multi-dimensional matrix product. It implies the

W [2]

hardness of the problem of computing the k-dimensional Boolean matrix product. Finally, we provide an efficient reduction of the problem of finding the lowest common ancestors for all k-tuples of vertices in a directed acyclic graph to the problem of finding witnesses of the Boolean variant of the multi-dimensional matrix product. Although the time complexities of the algorithms resulting from the aforementioned reductions solely match those of the known algorithms, the advantage of our algorithms is simplicity. Our algorithms also demonstrate the versatility of the multi-dimensional matrix product framework. Full article

► Show Figures

Figure 1

17 pages, 812 KiB

Open AccessArticle

Weibull-Open-World (WOW) Multi-Type Novelty Detection in CartPole3D

by Terrance E. Boult, Nicolas M. Windesheim, Steven Zhou, Christopher Pereyda and Lawrence B. Holder

Algorithms 2022, 15(10), 381; https://0-doi-org.brum.beds.ac.uk/10.3390/a15100381 - 18 Oct 2022

Cited by 2 | Viewed by 1507

Abstract

Algorithms for automated novelty detection and management are of growing interest but must address the inherent uncertainty from variations in non-novel environments while detecting the changes from the novelty. This paper expands on a recent unified framework to develop an operational theory for novelty that includes multiple (sub)types of novelty. As an example, this paper explores the problem of multi-type novelty detection in a 3D version of CartPole, wherein the cart Weibull-Open-World control-agent (WOW-agent) is confronted by different sub-types/levels of novelty from multiple independent agents moving in the environment. The WOW-agent must balance the pole and detect and characterize the novelties while adapting to maintain that balance. The approach develops static, dynamic, and prediction-error measures of dissimilarity to address different signals/sources of novelty. The WOW-agent uses the Extreme Value Theory, applied per dimension of the dissimilarity measures, to detect outliers and combines different dimensions to characterize the novelty. In blind/sequestered testing, the system detects nearly 100% of the non-nuisance novelties, detects many nuisance novelties, and shows it is better than novelty detection using a Gaussian-based approach. We also show the WOW-agent’s lookahead collision avoiding control is significantly better than a baseline Deep-Q-learning Networktrained controller. Full article

► Show Figures

Figure 1

14 pages, 2888 KiB

Open AccessArticle

Computational Complexity of Modified Blowfish Cryptographic Algorithm on Video Data

by Abidemi Emmanuel Adeniyi, Sanjay Misra, Eniola Daniel and Anthony Bokolo, Jr.

Algorithms 2022, 15(10), 373; https://0-doi-org.brum.beds.ac.uk/10.3390/a15100373 - 10 Oct 2022

Cited by 7 | Viewed by 2178

Abstract

Background: The technological revolution has allowed users to exchange data and information in various fields, and this is one of the most prevalent uses of computer technologies. However, in a world where third parties are capable of collecting, stealing, and destroying information without authorization, cryptography remains the primary tool that assists users in keeping their information secure using various techniques. Blowfish is an encryption process that is modest, protected, and proficient, with the size of the message and the key size affecting its performance. Aim: the goal of this study is to design a modified Blowfish algorithm by changing the structure of the F function to encrypt and decrypt video data. After which, the performance of the normal and modified Blowfish algorithm will be obtained in terms of time complexity and the avalanche effect. Methods: To compare the encryption time and security, the modified Blowfish algorithm will use only two S-boxes in the F function instead of the four used in Blowfish. Encryption and decryption times were calculated to compare Blowfish to the modified Blowfish algorithm, with the findings indicating that the modified Blowfish algorithm performs better. Results: The Avalanche Effect results reveal that normal Blowfish has a higher security level for all categories of video file size than the modified Blowfish algorithm, with 50.7176% for normal Blowfish and 43.3398% for the modified Blowfish algorithm of 187 kb; hence, it is preferable to secure data and programs that demand a high level of security with Blowfish. Conclusions: From the experimental results, the modified Blowfish algorithm performs faster than normal Blowfish in terms of time complexity with an average execution time of 250.0 ms for normal Blowfish and 248.4 ms for the modified Blowfish algorithm. Therefore, it can be concluded that the modified Blowfish algorithm using the F-structure is time-efficient while normal Blowfish is better in terms of security. Full article

► Show Figures

Figure 1

21 pages, 1957 KiB

Open AccessArticle

Quantum Computing Approaches for Mission Covering Optimization

by Massimiliano Cutugno, Annarita Giani, Paul M. Alsing, Laura Wessing and Austar Schnore

Algorithms 2022, 15(7), 224; https://0-doi-org.brum.beds.ac.uk/10.3390/a15070224 - 27 Jun 2022

Cited by 4 | Viewed by 1656

Abstract

Quantum computing has the potential to revolutionize the way hard computational problems are solved in terms of speed and accuracy. Quantum hardware is an active area of research and different hardware platforms are being developed. Quantum algorithms target each hardware implementation and bring advantages to specific applications. The focus of this paper is to compare how well quantum annealing techniques and the QAOA models constrained optimization problems. As a use case, a constrained optimization problem called mission covering optimization is used. Quantum annealing is implemented in adiabatic hardware such as D-Wave, and QAOA is implemented in gate-based hardware such as IBM. This effort provides results in terms of cost, timing, constraints held, and qubits used. Full article

► Show Figures

Figure 1

23 pages, 1335 KiB

Open AccessArticle

Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm

by Franz Georg Fuchs, Kjetil Olsen Lye, Halvor Møll Nilsen, Alexander Johannes Stasik and Giorgio Sartor

Algorithms 2022, 15(6), 202; https://0-doi-org.brum.beds.ac.uk/10.3390/a15060202 - 10 Jun 2022

Cited by 12 | Viewed by 2626

Abstract

The quantum approximate optimization algorithm/quantum alternating operator ansatz (QAOA) is a heuristic to find approximate solutions of combinatorial optimization problems. Most of the literature is limited to quadratic problems without constraints. However, many practically relevant optimization problems do have (hard) constraints that need to be fulfilled. In this article, we present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space given by these constraints. We generalize the “XY”-mixer designed to preserve the subspace of “one-hot” states to the general case of subspaces given by a number of computational basis states. We expose the underlying mathematical structure which reveals more of how mixers work and how one can minimize their cost in terms of the number of CX gates, particularly when Trotterization is taken into account. Our analysis also leads to valid Trotterizations for an “XY”-mixer with fewer CX gates than is known to date. In view of practical implementations, we also describe algorithms for efficient decomposition into basis gates. Several examples of more general cases are presented and analyzed. Full article

► Show Figures

Figure 1

17 pages, 869 KiB

Open AccessArticle

Two Taylor Algorithms for Computing the Action of the Matrix Exponential on a Vector

by Javier Ibáñez, José M. Alonso, Pedro Alonso-Jordá, Emilio Defez and Jorge Sastre

Algorithms 2022, 15(2), 48; https://0-doi-org.brum.beds.ac.uk/10.3390/a15020048 - 28 Jan 2022

Cited by 3 | Viewed by 2362

Abstract

The action of the matrix exponential on a vector

e^{A t} v

A \in C^{n \times n}

v \in C^{n}

, appears in problems that arise in mathematics, physics, and engineering, such as the solution of systems of [...] Read more.

The action of the matrix exponential on a vector

e^{A t} v

A \in C^{n \times n}

v \in C^{n}

, appears in problems that arise in mathematics, physics, and engineering, such as the solution of systems of linear ordinary differential equations with constant coefficients. Nowadays, several state-of-the-art approximations are available for estimating this type of action. In this work, two Taylor algorithms are proposed for computing

e^{A} v

, which make use of the scaling and recovering technique based on a backward or forward error analysis. A battery of highly heterogeneous test matrices has been used in the different experiments performed to compare the numerical and computational properties of these algorithms, implemented in the MATLAB language. In general, both of them improve on those already existing in the literature, in terms of accuracy and response time. Moreover, a high-performance computing version that is able to take advantage of the computational power of a GPU platform has been developed, making it possible to tackle high dimension problems at an execution time significantly reduced. Full article

► Show Figures

Figure 1

20 pages, 368 KiB

Open AccessArticle

Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems

by Kelin Luo and Frits C. R. Spieksma

Algorithms 2022, 15(2), 30; https://0-doi-org.brum.beds.ac.uk/10.3390/a15020030 - 18 Jan 2022

Cited by 1 | Viewed by 2219

Abstract

Motivated by applications in ride-sharing and truck-delivery, we study the problem of matching a number of requests and assigning them to cars. A number of cars are given, each of which consists of a location and a speed, and a number of requests are given, each of which consists of a pick-up location and a drop-off location. Serving a request means that a car must first visit the pick-up location of the request and then visit the drop-off location. Each car can only serve at most c requests. Each assignment can yield multiple different serving routes and corresponding serving times, and our goal was to serve the maximum number of requests with the minimum travel time (called

{CS}_{s u m}

) and to serve the maximum number of requests with the minimum total latency (called

{CS}_{l a t}

). In addition, we studied the special case where the pick-up and drop-off locations of a request coincide. Both problems

{CS}_{s u m}

and

{CS}_{l a t}

are APX-hard when

c \geq 2

. We propose an algorithm, called the transportation algorithm (TA), which is a

(2 c - 1)

-approximation (resp. c-approximation) algorithm for

{CS}_{s u m}

(resp.

{CS}_{l a t}

); these bounds are shown to be tight. We also considered the special case where each car serves exactly two requests, i.e.,

c = 2

. In addition to the TA, we investigated another algorithm, called the match-and-assign algorithm (MA). Moreover, we call the algorithm that outputs the best of the two solutions found by the TA and MA the CA. We show that the CA is a two-approximation (resp.

5 / 3

) for

{CS}_{s u m}

(resp.

{CS}_{l a t}

), and these ratios are better than the ratios of the individual algorithms, the TA and MA. Full article

► Show Figures

Figure 1

Journal Menu

Journal Browser

Feature Paper in Algorithms and Complexity Theory

Share This Topical Collection

Editor

Topical Collection Information

Keywords

Published Papers (13 papers)

2023

Jump to: 2022

2022

Jump to: 2023

Further Information

Guidelines

MDPI Initiatives

Follow MDPI