Lecture

Submodular Function Minimization

Description

This lecture covers the concept of submodular functions and their minimization, defining submodularity as f(A) + f(B) >= f(AUB) + f(AMB) for all A, B subsets of the ground set N. It also explains the intuition behind submodularity, focusing on diminishing returns. Examples of submodular functions, such as graph cut functions, are provided to illustrate the concept. The instructor discusses the Lovász Extension and its role in submodular function minimization, emphasizing the uniformity of the extension. The lecture concludes with the application of submodular functions in influence maximization, where the goal is to select a set of individuals to maximize the spread of influence in a network.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.