Тел.: +7 (495) 772-95-90 * 12332
125319, Москва, Кочновский проезд, д. 3 (недалеко от станции метро "Аэропорт").
Декан — Аржанцев Иван Владимирович
Первый заместитель декана факультета — Вознесенская Тамара Васильевна
Заместитель декана по научной работе и международным связям — Объедков Сергей Александрович
Заместитель декана по административно-финансовой работе — Плисецкая Ирина Александровна
A perfect 2-matching in an undirected graph G=(V,E) is a function x:E→0,1,2 such that for each node v∈V the sum of values x(e) on all edges e incident to v equals 2. If supp(x)=e∈E∣x(e)≠0 contains no triangles then x is called triangle-free. Polyhedrally speaking, triangle-free 2-matchings are harder than 2-matchings, but easier than usual 1-matchings. Given edge costs c:E→R + , a natural combinatorial problem consists in finding a perfect triangle-free matching of minimum total cost. For this problem, Cornuéjols and Pulleyblank devised a combinatorial strongly-polynomial algorithm, which can be implemented to run in O(VElogV) time. (Here we write V, E to indicate their cardinalities |V|, |E|.) If edge costs are integers in range [0,C] then for both 1- and 2-matchings some faster scaling algorithms are known that find optimal solutions within O(Vα(E,V)logVElog(VC)) and O(VElog(VC)) time, respectively, where α denotes the inverse Ackermann function. So far, no efficient cost-scaling algorithm is known for finding a minimum-cost perfect triangle-free2-matching. The present paper fills this gap by presenting such an algorithm with time complexity of O(VElogVlog(VC)).
This volume contains the refereed proceedings of the 6th International Conference on Analysis of Images, Social Networks, and Texts (AIST 2017)1. The previous conferences during 2012–2016 attracted a significant number of students, researchers, academics, and engineers working on interdisciplinary data analysis of images, texts, and social networks. The broad scope of AIST made it an event where researchers from different domains, such as image and text processing, exploiting various data analysis techniques, can meet and exchange ideas. We strongly believe that this may lead to cross fertilisation of ideas between researchers relying on modern data analysis machinery. Therefore, AIST brought together all kinds of applications of data mining and machine learning techniques. The conference allowed specialists from different fields to meet each other, present their work, and discuss both theoretical and practical aspects of their data analysis problems. Another important aim of the conference was to stimulate scientists and people from industry to benefit from the knowledge exchange and identify possible grounds for fruitful collaboration. The conference was held during July 27–29, 2017. The conference was organised in Moscow, the capital of Russia, on the campus of Moscow Polytechnic University. This year, the key topics of AIST were grouped into six tracks: 1. General topics of data analysis chaired by Sergei Kuznetsov (Higher School of Economics, Russia) and Amedeo Napoli (LORIA, France) 2. Natural language processing chaired by Natalia Loukachevitch (Lomonosov Moscow State University, Russia) and Alexander Panchenko (University of Hamburg, Germany) 3. Social network analysis chaired by Stanley Wasserman (Indiana University, USA) 4. Analysis of images and video chaired by Victor Lempitsky (Skolkovo Institute of Science and Technology, Russia) and Andrey Savchenko (Higher School of Economics, Russia) 5. Optimisation problems on graphs and network structures chaired by Panos Pardalos (University of Florida, USA) and Michael Khachay (IMM UB RAS and Ural Federal University, Russia) 6. Analysis of dynamic behaviour through event data chaired by Wil van der Aalst (Eindhoven University of Technology, The Netherlands) and Irina Lomazova (Higher School of Economics, Russia) One of the novelties this year was the introduction of a new specialised track on process mining (Track 6).
This paper presents a modular approach to discover process models for multi-agent systems from event logs. System event logs are filtered according to individual agent behavior. We discover workflow nets for each agent using existing process discovery algorithms. We consider asynchronous interactions among agents. Given a specification of an interaction protocol, we propose a general scheme of workflow net composition. By using morphisms, we prove that this composition preserves soundness of components. A quality evaluation shows the increase in the precision of models discovered by the proposed approach.
Coordination of several distributed system components is an error-prone task, since interaction of several simple components can generate rather sophisticated behavior. Verification of such systems is very difficult or even impossible because of the so-called state space explosion problem, when the size of the system reachability set grows exponentially on the number of interacting agents. To overcome this problem several approaches to construct correct models of interacting agents in a compositional way were proposed in the literature. They define different properties and conditions to ensure correct behavior of interacting agents. Checking these conditions may be in its turn quite a problem. In this paper, we propose patterns for correct composition of component models. For justifying these patterns we use special net morphisms. However, to apply patterns the user does not need to be familiar with the underlying theory.