Submodularity and Valued Constraint Satisfaction Problems

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

• Stanislav Zivny - University of Oxford
• Monday 12 April 2010, 14:00-15:00
• Small public lecture room, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• Microsoft Research Cambridge, public talks
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Small public lecture room, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.