In computer vision and machine learning combinatorial optimization
problems are widespread, typically NP-hard and tend to pose unique
challenges due to their very large scale and problem structure.
Established techniques from the mathematical optimization community
cannot cope with the encountered problem sizes and do not exploit
special problem characteristics. In this talk I will present several
new solution paradigms for solving large scale combinatorial problems
in computer vision efficiently and to high accuracy. I will discuss
how these principles can be applied on classical problems of
combinatorial optimization that have found wide use in computer
vision, machine learning and computer graphics, namely inference in
Markov Random Fields, the quadratic assignment problem and graph
decomposition. Lastly, I will show empirical results showing the great
practical performance of the presented techniques.