Лаборатория ЛАТАС и компания Яндекс проводят рабочий семинар "Прикладные задачи оптимизации и поиска в сетях (на графах)"

Семинар будет проходить с 11:00 до 16:00 6 апреля, 2015. 
Место проведения семинара: офис компании Яндекс  (Метро «Парк культуры»)

Участники от лаборатории ЛАТАС:

Пардалос П.М. – заслуженный профессор университета Флориды, США. Научный руководитель лаб. ЛАТАС

Калягин В.А. – профессор НИУ ВШЭ, зав. лаб. ЛАТАС

Бацын М.В. – ведущий научный сотрудник ЛАТАС

Малышев Д.С. - ведущий научный сотрудник ЛАТАС

Пономаренко А.А. – научный сотрудник ЛАТАС

Савченко А.В. – старший научный сотрудник ЛАТАС

Доклады сотрудников лаборатории:

Бацын Михаил Владимирович. Прикладные задачи оптимизации

Калягин Валерий Александрович. Задачи идентификации сетевых структур

Малышев Дмитрий Сергеевич.  Критические классы для алгоритмических задач на графах

Пономаренко Александр Александрович. Организация данных для распределенного поиска

Савченко Андрей Владимирович.  Методы распознавания изображений в условиях малых выборок

Аннотации докладов сотрудников:

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