Discrete energy minimization - part 2

Discrete energy minimization (also known as MAP inference in graphical models or weighted constraint satisfaction) has many applications e.g. in computer vision, machine learning, and bioinformatics. Last two decades have seen a big progress on tackling this NP-hard problem. I will try to taxonomize and explain these results, biased by my own research. You will hear about graph cuts, submodularity, linear programming relaxation, message passing algorithms, fractional polymorphisms. The lecture will be "applied mathematical" with emphasis on algorithms.