The founders and the publisher of the online journal “Software Journal: Theory and Applications” announce the termination of the media from November 1, 2022.
Instead, we are waiting for you on the pages of the top-rated journal “Software & Systems”.
The design of the algorithm reduction of a binary cooperative assignment problem to a travelling salesman problem
The paper considers the pressing problem of reducing some NP-complete problems to others. The primary focus in this paper is the design of the algorithm reduction of a binary cooperative assignment problem to a travelling salesman problem to find its solution and transfer the solving performance of one NP-complete problem to another; there are brief mathematical formulations of the problems.
The paper describes the problems associated with reducing some NP-complete problems to others. As a sample, we consider an example of reducing the traveling salesman problem to the problem of the Hamiltonian cycle. The authors propose a new algorithm for reducing a binary cooperative assignment problem to a travelling salesman problem, which solves the current reduction problems that impose constraints on the NP-complete problems themselves.
The authors investigate the developed algorithm for reducing the accuracy of obtaining the result of the original NP-complete problem and the computational complexity.
The paper mathematically proves that the reduction algorithm does not reduce the accuracy of obtaining a solution to the binary cooperative assignment problem when the salesman problem is accurately solved. There are no restrictions on the problems themselves. The paper contains a mathematical argument for the polynomial computational complexity of the developed reduction algorithm.
For software demonstration of the correct operation, the developed reduction algorithm was implemented in the Java programming language, as well as exact algorithms for solving the binary cooperative assignment problem and the traveling salesman problem.
In this program, experiments were performed to find solutions to the original NP-complete problem with different amounts of input data, and the correctness of the reduction algorithm was confirmed.
The paper describes future trends for the analysis of this area.
Analysis of X Windows System and Hardware Interaction Methods
This article describes several methods that the X Windows System interacts with hardware. The basic 2D hardware acceleration operations were examined using the EXA architecture as an example. Xorg was tested with x11perf version 1.5 to examine the performance.
Testing was carried out in 5 modes, i.e. with 2D hardware acceleration and without. The test results lead to the conclusion that the use of 2D hardware acceleration with EXA is justified when high-resolution images are to be used or it is necessary to reduce the load on the CPU.
Performance testing with disabled hardware interaction (2D GPU + dummy EXA) showed that the use of EXA significantly affects the test rate as 2D GPU + dummy EXA driver performs better compared to the modesetting driver only with a certain set of tests. It’s worth noting that the use of EXA with the DRM stack has to be studied further, since, in most cases, scaling, pixmap copying, solid color filling, and other operations are processed by the CPU when using the DRM stack with the EXA_MIXED_PIXMAPS option. In certain situations, the absence of this option can lead to many visual artifacts in the form of unrendered areas of the image when updating the framebuffer.
The review of human identification techniques by facial image
This paper discusses modern methods and technologies for identification techniques by facial image.
All known approaches are based on the selection and analysis of face parameters in the image and their further processing. Processing the obtained face parameters is mainly based on neural network and mathematical approaches. The disadvantages of the neural network approach are mathematical problems (retraining, choosing
the optimization step, getting into a local optimum).
The problems of the mathematical approach are low speed and low resistance to the image defects, while
the neural network method can correct image defects at the stage of image alignment. Also, the mathematical method is very demanding in terms of computing resources.
During the work on the paper, the method of active form models and the neural network method of identifying a person by the image of a person were selected and tested on two data samples. The active shape model method is used to detect facial features and obtain key points on faces. The neural network method using a convolutional neural network retrieves a descriptor that describes a person, which is a vector of 128 features. Further, by determining the distance between the vectors, the most similar vector is located in the database.
During testing, the speed of the method and the accuracy of the work were measured. The test results showed a performance of approximately 2 secs in two samples and an accuracy of 97 %. These studies are related to the development and implementation of a module for streaming identification of people by video stream, where the reaction speed of the method is very important, as well as its accuracy.