Discrete Optimization

Vladimir Kolmogorov

The work of Vladimir Kolmogorov's group can be subdivided into three topics. The first one is development of efficient algorithms for inference in graphical models and combinatorial optimization problems. Some of the developed 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 of the group is theoretical investigations of the complexity of discrete optimization, in particular using the framework of Valued Constraint Satisfaction Problems and its variants. Finally, Kolmogorov's group has worked on applications of discrete optimization in computer vision such as image segmentation and stereo reconstruction.

Vladimir Kolmogorov
Institute of Science and Technology Austria (IST Austria)
Am Campus 1
A – 3400 Klosterneuburg
Tel.: +43 (0)2243 9000-4801
E-mail: vladimir.kolmogorov@remove-this.ist.ac.at


Vladimir Kolmogorov's website

Astrid Bonventre-Darthe
Phone: +43 (0)2243 9000-1194
E-mail: astrid.bonventre-darthe@remove-this.ist.ac.at


  • Alexandr Kazda, Postdoc
  • Michael Rolinek, PhD Student
  • Paul Swoboda, Postdoc

Open Position

In the group of Professor Vladimir Kolmogorov a postdoc position in the area of discrete optimization is available immediately. For detailed information see the postdoc ad.

Selected Publications

  • Kolmogorov V, Krokhin A, Rolínek M. The Complexity of General-Valued CSPs. In IEEE Symposium on Foundations of Computer Science (FOCS). October 2015.
  • Gridchyn I, Kolmogorov V. 2013. “Potts model, parametric maxflow and k-submodular functions”. In IEEE International Conference on Computer Vision (ICCV), Sydney, Australia.
  • Kolmogorov V. 2009. Blossom V: A new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation. 1(1), 43-67


Since 2014 Professor, IST Austria
2011-2014 Assistant Professor, IST Austria
2005-2011 Lecturer, University College London, UK
2003-2005 Assistant Researcher, Microsoft Research, Cambridge, UK
2003 PhD, Cornell University, USA

Selected Distinctions

2013 ERC Consolidator Grant
2012 Koenderink Prize at the European Conference on Computer Vision for fundamental contributions to computer vision
2007 Honorable mention, outstanding student paper award (to M. Pawan Kumar) at Neural Information Processing Systems Conference
2006-2011 The Royal Academy of Engineering/EPSRC Research Fellowship
2005 Best paper honorable mention award at IEEE Conference on Computer Vision and Pattern Recognition
2002 Best paper award at the European Conference on Computer Vision

To top