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

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Submodularity and Valued Constraint Satisfaction Problems

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Faculty of Asian & Middle Eastern Studies, Sidgwick Avenue The Arts Picturehouse Wolfson Lecture Hall, Churchill College

Other talks

Online Causal Inference Seminar FILM: One With The Whale Title TBC TOWARD AFFORDABLE PREVENTIVE HEALTHCARE: How basic science addresses grand challenges Dinner Market Failure, Organ Shortage, Pandemic and Climate Change: The Architecture of Cooperation
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity