# LATNA lab. and Yandex company orginize a seminar "Application of the optimization and search problems in networks (on graphs)"

The seminar will take place in Nizhny Novgorod, in the office of Yandex Co. (M. "Park Kultury"). The seminar will start at 11a.m. on April 6.

**Participants from LATNA lab.:**

Panos M. Pardalos - Distinguished Professor of Industrial and Systems Engineering at the University of Florida (the USA), the Scientific Advisor of LATNA lab.

Valery A. Kalyagin - Tenured Professor at the NRU HSE, the Head of LATNA lab.

Michael V. Batsyn - the Leading Researcher of LATNA lab.

Dmitry S. Malyshev - the Leading Researcher of LATNA lab.

Alexander A. Ponomarenko - the Researcher of LATNA lab.

Andrey V. Savchenko - the Researcher of LATNA lab.

**Annotations of the given talks:**

Batsyn M.V. Applied optimization problems

The talk will be devoted to modern approach for following optimization problems

1. Real life vehicle routing problem

2. Optimization in warehousing

3. Scheduling problem with multi processors

Kalyagin V.A. Problems of identification of network structures

For a complex networks a filtration technique is usually used to extract a valuable information of network structures. Traditional network structures are: maximum spanning tree, maximally filtered planar graph, threshold graph, maximum cliques and independent sets in threshold graph and others. Statistical origin of the data implies a necessity to solve an identification problem. The talk will be devoted to a recent and new approach to identification problem on the basis of multiple decision theory ((Multiple decision statistical procedures, multiple test procedures). This approach gives possibility to develop a methods for statistical uncertainty estimation and to design optimal and robust identification statistical procedures. It turns out that statistical procedures based on the probability of sign coincidence are more appropriate than statistical procedures based on classical Pearson correlations. Some applications to stock market analysis will be discussed.

Malyshev D.S. Critical graph classes for algorithmic graph problems

The evolution of computational complexity theory contributed to growing in a pessimistic viewpont on a possibility for the existence of polynomial-time algorithms for solving many graph problems having a theoretical or practical interest. Narrowing is one of possible ways to overcome the complexity of such problems. It is to impose additional restrictions on a class of graphs. Sometimes, taking these restrictions into account leads to development of a polynomial-time algorithm for solving a problem. Sometimes, it is possible to prove that a problem is NP-complete for a class. A large set of facts about polynomial-time solvability and NP-completeness of diverse graph problems under various restrictions of input data is known to the date. This process becomes more focused and systematic when representative families of graph classes are considered. In the talk, we consider graph classes closed under isomorphism and vertex deletion (hereditary classes), as well as discovering critical classes that play a determinative role in the analysis of the computational complexity in the family of hereditary classes.

Ponomarenko A.A. How to organize information for decentralized search.

In the talk we discuss how to organize information into a network in which atomic data (information object) are associated with nodes. The network is built with a similarity measure which is defined on the set of all possible pairs of objects from the domain. The network is constructed in such a way that the search algorithm, represented by greedy walk, can efficiently solve the nearest neighbor problem using only local information, i.e. greedy walk algorithm has the ability to efficiently find a node which contains the information object closest to a given arbitrary query object by similarity measure. Such an approach can serve as a base for building global decentralized storages with ability to perform similarity search. Moreover, such an approach can become the foundation for a new principle of publishing and searching information in the Internet.

Savchenko A.V. Small sample size problem in image recognition

In this presentation we explore the problem of insufficient accuracy and performance of modern image classification methods if the database contains thousand of classes and only small number of samples per class are available. We describe a new approach to design classifiers based on representation of image as a piecewise-regular object and testing for segment homogeneity. Finally, we present experimental study results in recognition of faces, visems (visual representation of vowel phonemes) and video-based moving forklift truck detection