# Publications

In this study we consider the shortest path problem, where the arc costs are subject to distributional uncertainty. Basically, the decision-maker attempts to minimize her worst-case expected loss over an ambiguity set (or a family) of candidate distributions that are consistent with the decision-maker's initial information. The ambiguity set is formed by all distributions that satisfy prescribed linear first-order moment constraints with respect to subsets of arcs and individual probability constraints with respect to particular arcs. Under some additional assumptions the resulting distributionally robust shortest path problem (DRSPP) admits equivalent robust and mixed-integer programming (MIP) reformulations. The robust reformulation is shown to be NP-hard, whereas the problem without the first-order moment constraints is proved to be polynomially solvable. We perform numerical experiments to illustrate the advantages of the considered approach; we also demonstrate that the MIP reformulation of DRSPP can be solved effectively using off-the-shelf solvers.

In this paper, we consider a class of orientation-preserving Morse–Smale diffeomorphisms defined on an orientable surface. The papers by Bezdenezhnykh and Grines showed that such diffeomorphisms have a finite number of heteroclinic orbits. In addition, the classification problem for such diffeomorphisms is reduced to the problem of distinguishing orientable graphs with substitutions describing the geometry of a heteroclinic intersection. However, such graphs generally do not admit polynomial discriminating algorithms. This article proposes a new approach to the classification of these cascades. For this, each diffeomorphism under consideration is associated with a graph that allows the construction of an effective algorithm for determining whether graphs are isomorphic. We also identified a class of admissible graphs, each isomorphism class of which can be realized by a diffeomorphism of a surface with an orientable heteroclinic. The results obtained are directly related to the realization problem of homotopy classes of homeomorphisms on closed orientable surfaces. In particular, they give an approach to constructing a representative in each homotopy class of homeomorphisms of algebraically finite type according to the Nielsen classification, which is an open problem today.

The article is considering the problem of increasing the performance and accuracy of video face identification. We examine the selection of the several best video frames using various techniques for assessing the quality of images. In contrast to traditional methods with estimation of image brightness/contrast, we propose to utilize the deep learning techniques that estimate the frame quality by using the lightweight convolutional neural network. In order to increase the effectiveness of the frame quality assessment step, we propose to distill knowledge of the cumbersome existing FaceQNet model for which there is no publicly available training dataset. The selected *K*-best frames are used to describe an input set of frames with a single average descriptor suitable for the nearest neighbor classifier. The proposed algorithm is compared with the traditional face feature extraction for each frame, as well as with the known clustering methods for a set of video frames.

A novel image recognition algorithm based on sequential three-way decisions is introduced to speed up the inference in a convolutional neural network. In contrast to the majority of existing studies, our approach does not require a special procedure to train a neural network, and thus it can be used with arbitrary architectures including pre-trained convolutional nets. Each image is associated with a sequence of features extracted at different layers of the neural network. Features from earlier layers stand for coarse-grained image representation. Fine-grained representations include embeddings from one of later layers. Confidence scores of classifiers representing the input image at each granularity level are computed in order to populate a set of unlikely classes with low confidence scores. The thresholds for these scores are chosen by using the step-up multiple testing procedure. The categories from this set are not considered at the next levels with finer granularity. The algorithm selecting the granularity levels and thresholds for each level is trained on a small sample. An experimental study for several datasets and neural architectures demonstrated that the proposed approach reduces the running time by up to 40% with a controllable decrease in accuracy.

We consider the maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance (denoted by (MSPITH)), which has wide applications in transportation network, networkwar and terrorist network. The problem (MSPITH) aims to maximize the length of the shortest path from the root of a tree to all its leaves by upgrading edge weights such that the upgrade cost under sum-Hamming distance is upper-bounded by a given value. We show that the problem (MSPITH) under weighted sum-Hamming distance is NP-hard. We consider two cases of the problem (MSPITH) under unit sum-Hamming distance based on the number K of critical edges. We propose a greedy algorithm within O(n + l log l) time when K = 1 and a dynamic programming algorithm within O(n(log n + K3)) time when K > 1, where n and l are the numbers of nodes and leaves in a tree, respectively. Furthermore, we consider a minimum cost shortest path interdiction problem by upgrading edges on trees under unit Hamming distance, denoted by (MCSPITUH) and propose a binary search algorithm within O(n4 log n) time, where a dynamic programming algorithm is executed in each iteration to solve its corresponding problem (MSPITH). Finally, we design numerical experiments to show the effectiveness of the algorithms.

The present paper discusses the problem of distortions in speech signals transmitted over a communication channel to a biometric system during voice-based remote identification. A possible rectification approach involves a preliminary correction of the frequency spectrum of the received signal based on the pre-distortion principle. Taking into account a priori uncertainty, a new information indicator of speech signal distortions is proposed, along with a method for its measurement under conditions of small observation samples. An example of fast practical implementation of the method based on a parametric spectral analysis algorithm is considered. Results of an experimental test of the proposed approach are provided for three different communication channel instantiations. It is shown that the proposed method facilitates the transformation of an initially distorted speech signal into compliance with a registered voice template using an acceptable algorithmic information discrimination criterion. The described approach may be used in existing biometric systems and speaker identification technologies.

The vertex 3-colourability problem is to verify whether it is possible to split the vertex set of a given graph into three subsets of pairwise nonadjacent vertices or not. This problem is known to be NP-complete for planar graphs of the maximum face length at most 4 (and, even, additionally, of the maximum vertex degree at most 5), and it can be solved in linear time for planar triangulations. Additionally, the vertex 3-colourability problem is NP-complete for planar graphs of the maximum vertex degree at most 4, but it can be solved in constant time for graphs of the maximum vertex degree at most 3. It would be interesting to investigate classes of planar graphs with simultaneously bounded length of faces and the maximum vertex degree and to find the threshold, for which the complexity of the vertex 3-colourability problem is changed from polynomial-time solvability to NP-completeness. In this paper, we prove NP-completeness of the vertex 3-colourability problem for planar graphs of the maximum vertex degree at most 4, whose faces are of length no more than 5.

It is a well known fact that any smooth manifold admits a Morse function, whereas the problem of existence of a Morse function for a topological manifold stated by Marston Morse in 1959 is still open. In the present paper we prove that a topological manifold admits a continuous Morse function if it admits a topological flow with a finite hyperbolic chain recurrent set. We construct this function as a Lyapunov function whose set of the critical points coincides with the chain recurrent set of the flow.

This book constitutes revised selected papers of the 9th International Conference on Analysis of Images, Social Networks and Texts, AIST 2020, held in Moscow, Russia, in october 2020. Due to the COVID-19 pandemic the conference was held online.

The 14 full papers, 9 short papers and 4 poster papers were carefully reviewed and selected from 108 qualified submissions. The papers are organized in topical sections on natural language processing; computer vision; social network analysis; data analysis and machine learning; theoretical machine learning and optimization; process mining; posters.

Two market network models are investigated. One of them is based on the classical Pearson correlation as the measure of association between stocks returns, whereas the second one is based on the sign similarity measure of association between stocks returns. We study the uncertainty of identification procedures for the following market network characteristics: distribution of weights of edges, vertex degree distribution in the market graph, cliques and independent sets in the market graph, and the vertex degree distribution of the maximum spanning tree. We define the true network characteristics, the losses from the error of its identification by observations, and the uncertainty of identification procedures as the expected value of losses. We use elliptically contoured distribution as a model of multivariate stocks returns distribution. It is shown that identification statistical procedures based on the sign similarity are statistically robust in contrast to the procedures based on the classical Pearson correlation

In this paper, we show that the weighted vertex coloring problem can be solved in polynomial on the sum of vertex weights time for {P_5, K_{2,3}, K_{2,3}^+}-free graphs. As a corollary, this fact implies polynomial-time solvability of the unweighted vertex coloring problem for {P_5, K_{2,3}, K_{2,3}^+}-free graphs. As usual, P_5 and K_{2,3} stands, respectively, for the simple path on 5 vertices and for the biclique with the parts of 2 and 3 vertices, K_{2,3} denotes the graph, obtained from a K_{2,3} by joining its degree 3 vertices with an edge.

We consider the lower bounded inverse optimal value problem on minimum spanning tree under unit l∞lnorm. Given an edge weighted connected undirected network G=(V,E,w), a spanning tree T0, a lower bound vector l and a value *K*, we aim to find a new weight vector w respecting the lower bound such that T0 is a minimum spanning tree under the vector w with weight *K*, and the objective is to minimize the modification cost under unit l∞ norm. We present a mathematical model of the problem. After analyzing optimality conditions of the problem, we develop a strongly polynomial time algorithm with running time *O*(|*V*||*E*|). Finally, we give an example to demonstrate the algorithm and present the numerical experiments.

The vertex colourability problem is to determine, for a given graph and a given natural *k*, whether it is possible to split the graph’s vertex set into at most *k* subsets, each of pairwise non-adjacent vertices, or not. A hereditary class is a set of simple graphs, closed under deletion of vertices. Any such a class can be defined by the set of its forbidden induced subgraphs. For all but four hereditary classes, defined by a pair of connected five-vertex induced prohibitions, the complexity status of the vertex colourability problem is known. In this paper, we reduce the number of the open cases to three, by showing polynomial-time solvability of the problem for {claw,butterfly}{claw,butterfly}-free graphs. A *claw* is the star graph with three leaves, a *butterfly* is obtained by coinciding a vertex in a triangle with a vertex in another triangle.

A complete description of trees with maximal possible number of maximum independent setsamong all 𝑛-vertex trees with exactly 𝑙 leaves is obtained. For all values of the parameters 𝑛 and 𝑙, the extremal tree is unique and is the result of merging the endpoints of 𝑙 simple paths.

In this paper we consider the problem of vehicle assignment in heterogeneous fleet site-dependent Vehicle Routing Problems (VRP) with split deliveries. In such VRP problems vehicles can have different capacities, fixed and travel costs, and site-dependency constraints limit for every customer a set of vehicles, which can serve it. The Vehicle Assignment Problem (VAP) arises in heuristic and exact algorithms, when vehicles are assigned to all customers or one customer is added to the current vehicle route. The VAP objective is to minimize the total assignment cost while the cost of assigning a vehicle to a customer is computed in some heuristic way. Without split deliveries, when a delivery to a customer cannot be split between two vehicles, the VAP problem is modeled in literature as the Generalized Assignment Problem. We demonstrate that allowing split deliveries reduces the VAP to the Hitchcock Transportation Problem, which can be efficiently solved with Transportation Simplex Methods. We also consider a special case, which is not rare in practice, when all customers are partitioned into classes, where customers have the same set of vehicles able to serve them, and the vehicle sets for these classes form a sequence of nested sets. We show that in this case if the cost per demand unit of assigning a vehicle to a customer depends only on the vehicle, then the VAP problem can be solved by a linear algorithm.

In this paper fast image recognition techniques based on statistical sequential analysis are discussed. We examine the possibility to sequentially process the principal components and organize a convolutional neural net- work with early exits. Particular attention is paid to sequentially learn multi-task lightweight neural network model to predict several facial at- tributes (age, gender and ethnicity) based on preliminary training on the face classification task. It is highlighted that the whole above-mentioned model should be fine-tuned in order to deal with emotion recognition problem. Experimental study on several datasets demonstrate that the proposed approach is rather accurate and has very low run-time and space complexity when compared to known state-of-the-art methods.