Speaker: Vladimir Kolmogorov.

Title: Extensions of submodularity and their applications in computer vision

Abstract: Submodular functions have played a prominent role in computer vision
in the last decade; in many cases they can be minimized efficiently via graph cuts.
I will describe a larger class of functions that can be minimized in polynomial
time by solving a Basic Linear Programming relaxation of the problem.
It was recently shown that this is the the only tractable class of Finite-Valued
Constraint Satisfaction Problems (VCSPs), assuming that P != NP.

A special case of the new class is so-called k-submodular functions.
In the second part I will describe an application of k-submodular functions
to computing partially optimal solutions of certain NP-hard optimization problems.
In the case of the Potts energy function there is a close connection to
the approach proposed by Kovtun which also computes a part of an optimal solution.
I will show how to improve the complexity of the Kovtun's approach
from k to O(log k) maxflow computations, where k is the number of labels.
The algorithm generalizes the method of Felzenszwalb et al. for Tree Metrics,
and resembles a parametric maxflow algorithm.