Computer Science – Data Structures and Algorithms
Scientific paper
2009-12-02
Computer Science
Data Structures and Algorithms
This revision corrects an error in definition 2.2, as well as provides additional intuition regarding the definitions of conve
Scientific paper
Submodularity is a fundamental phenomenon in combinatorial optimization. Submodular functions occur in a variety of combinatorial settings such as coverage problems, cut problems, welfare maximization, and many more. Therefore, a lot of work has been concerned with maximizing or minimizing a submodular function, often subject to combinatorial constraints. Many of these algorithmic results exhibit a common structure. Namely, the function is extended to a continuous, usually non-linear, function on a convex domain. Then, this relaxation is solved, and the fractional solution rounded to yield an integral solution. Often, the continuous extension has a natural interpretation in terms of distributions on subsets of the ground set. This interpretation is often crucial to the results and their analysis. The purpose of this survey is to highlight this connection between extensions, distributions, relaxations, and optimization in the context of submodular functions. We also present the first constant factor approximation algorithm for minimizing symmetric submodular functions subject to a cardinality constraint.
No associations
LandOfFree
Submodular Functions: Extensions, Distributions, and Algorithms. A Survey does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Submodular Functions: Extensions, Distributions, and Algorithms. A Survey, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Submodular Functions: Extensions, Distributions, and Algorithms. A Survey will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-508245