Tutorials
Dr. Andrey Melnikov, Sobolev Institute of Mathematics, Russia
Practice of using the Gurobi optimizer
Abstract: The general-purpose optimization software has never been more powerful than today. It is universal, customizable, controllable, and enables a user with a variety of tools and features to get better solutions in a shorter time. In this tutorial, we will overview the ingredients of one of the fastest MIP solvers, the Gurobi optimizer, that are relevant in academic studies. The key topics would be the internal organization of the solver, its tuning when solving LPs and MIPs, the most newly added features, and other selected ones.
VIDEO (mp4.file 273 Mb)
VIDEO (mp4.file 273 Mb)
Prof. Alexander Grigoriev, Maastricht University, Netherlands
Evolution of sailor and surgical knots
Abstract:
This is a survey of recent developments in the computational knot theory. We start with retrospective of well-known results and techniques bringing topological knot theory and graph theory together: knots equivalence, Reidemeister moves, knot diagrams and knot polynomials. Then, we briefly address the complexity of the unknotting problem. We illustrate the difficulty of unknotting on small and insightful examples of knots. The easy unknotting cases, e.g., knot diagrams of treewidth 2, are addressed in details. We wrap up the tutorial posing numerous open questions and introducing new research directions.
VIDEO (mp4.file 153 Mb)
VIDEO (mp4.file 153 Mb)
Prof. Mikhail Khachay, Krasovsky Institute of Mathematics and Mechanics, Ekaterinburg, Russia
Metrics of a fixed doubling dimension: an efficient approximation
of combinatorial problems
Abstract For decades, for many well-known combinatorial optimization problems, the approximability results in the class of algorithms with theoretical performance guarantees have had the quite similar nature. For instance, the classic Traveling Salesman Problem (TSP) is stongly NP-hard both in general and even in very specific settings, e.g. in the Euclidean plane. The problem is hardly approximable in general setting, it is APX-complete for an arbitrary metric, whilst, the problem admits polynomial time approximation schemes (PTAS) in the Euclidean space of an arbitrary fixed dimension. Recent results in the field of the analysis of finite metric spaces shed a light to the design of approximation schemes for a wide family of metric settings of these problems. In this tutorial, we give a short overview of such an approach leading to the PTAS for the metric TSP in metric space of any fixed doubling dimension.
VIDEO (mp4.file 124 Mb)
VIDEO (mp4.file 124 Mb)
Prof. Vladimir V. Mazalov, Institute of Applied Mathematical Research, Petrozavodsk, Russia
Game Theory and Social Networks
Abstract Social networks represent a new phenomenon of our life. The growing popularity of social networks in the Web dates back to 1995 when American portal Classmates.com was launched. This project facilitated the soon appearance of online social networks (SixDegrees, LiveJournal, LinkedIn, MySpace, Facebook, Twitter, YouTube, and others) in the early 2000s. In Russia, the most popular networks are VKontakte and Odnoklassniki.
Social networks are visualized using social graphs. Graph theory provides main analysis tools for social networks. In particular, by calculating centrality measures for nodes and edges one may detect active participants (members) of a social network. We use for the analysis of social networks game-theoretic approach.
We propose a new concept of the betweenness centrality for weighted graphs using the methods of cooperative game theory. The characteristic function is determined by special way for different coalitions (subsets of the graph). The betweenness centrality is determined as the Myerson value. The results of computer simulations for some examples of networks, in particular, for the popular social network “VKontakte”, as well as the comparing with the PageRank method are presented. Then we apply game-theoretic methods for community detection in networks. Finally, for approaches based on potential games we suggest a very efficient computational scheme using Gibbs sampling.