University of Cambridge > > Microsoft Research Cambridge, public talks > Submodularity and Valued Constraint Satisfaction Problems

Submodularity and Valued Constraint Satisfaction Problems

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

Abstract: In this talk, I will present the concept of submdodularity and relate it to certain optimisation problems, which can be described as Valued Constraint Satisfaction Problems. This framework is equivalent to other frameworks, for instance, pseudo-Boolean polynomials, Gibbs energy minimisation or Markov Random Fields. It has previously been an open problem whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. We answer the problem negatively. We relate our results to the problem of which submodular functions can be minimised using the Min-Cut/Max-Flow techniques.

This talk is part of the Microsoft Research Cambridge, public talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2022, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity