In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an input set decreases as the size of the input set increases. Submodular functions have a natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory (as functions modeling user preferences) and electrical networks. Recently, submodular functions have also found immense utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains.
If is a finite set, a submodular function is a set function , where denotes the power set of , which satisfies one of the following equivalent conditions.
For every with and every we have that .
For every we have that .
For every and such that we have that .
A nonnegative submodular function is also a subadditive function, but a subadditive function need not be submodular.
If is not assumed finite, then the above conditions are not equivalent. In particular a function
defined by if is finite and if is infinite
satisfies the first condition above, but the second condition fails when and are infinite sets with finite intersection.
A set function is monotone if for every we have that . Examples of monotone submodular functions include:
Linear (Modular) functions Any function of the form is called a linear function. Additionally if then f is monotone.
Budget-additive functions Any function of the form for each and is called budget additive.
Coverage functions Let be a collection of subsets of some ground set . The function for is called a coverage function. This can be generalized by adding non-negative weights to the elements.
Entropy Let be a set of random variables.
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.
Some branches of economics and game theory deal with indivisible goods, discrete items that can be traded only as a whole. For example, in combinatorial auctions there is a finite set of items, and every agent can buy a subset of the items, but an item cannot be divided among two or more agents. It is usually assumed that every agent assigns subjective utility to every subset of the items. This can be represented in one of two ways: An ordinal utility preference relation, usually marked by .
In combinatorics, a branch of mathematics, a matroid ˈmeɪtrɔɪd is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.
Explores the convexity of Lovász extension and submodular function maximization, focusing on extending functions to convex sets and proving their convexity.
The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of f
A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper
In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...
Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...
We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call o ...