Vladimir Kolmogorov // Discrete Optimization

The work of Vladimir Kolmogorov’s group can be divided into three topics. The first is the development of efficient algorithms for inference in graphical models and combinatorial optimization problems. Some of their techniques are widely used in computer vision and other areas, for example the “Boykov-Kolmogorov” maximum flow algorithm and the “TRW-S” algorithm for MAP inference in pairwise graphical models. Kolmogorov’s “Blossom V” algorithm is currently the fastest technique in practice for computing a minimum cost perfect matching in a graph. The second focus is theoretical investigations of the complexity of discrete optimization, in particular using the framework of valued constraint satisfaction problems and their variants. Finally, the Kolmogorov group has worked on applications of discrete optimization in computer vision, such as image segmentation and stereo reconstruction.