Submodular Functions: Extensions, Distributions, and Algorithms. A Survey
---
paper_title: Submodular functions and convexity.

paper_content:

In “continuous” optimization convex functions play a central role. Besides elementary tools like differentiation, various methods for finding the minimum of a convex function constitute the main body of nonlinear optimization. But even linear programming may be viewed as the optimization of very special (linear) objective functions over very special convex domains (polyhedra). There are several reasons for this popularity of convex functions: ::: ::: ::: Convex functions occur in many mathematical models in economy, engineering, and other sciencies. Convexity is a very natural property of various functions and domains occuring in such models; quite often the only non-trivial property which can be stated in general.
---
paper_title: Submodular functions and convexity.

paper_content:

In “continuous” optimization convex functions play a central role. Besides elementary tools like differentiation, various methods for finding the minimum of a convex function constitute the main body of nonlinear optimization. But even linear programming may be viewed as the optimization of very special (linear) objective functions over very special convex domains (polyhedra). There are several reasons for this popularity of convex functions: ::: ::: ::: Convex functions occur in many mathematical models in economy, engineering, and other sciencies. Convexity is a very natural property of various functions and domains occuring in such models; quite often the only non-trivial property which can be stated in general.
---
paper_title: Maximizing Non-Monotone Submodular Functions

paper_content:

Submodular maximization generalizes many important problems including Max Cut in directed/undirected graphs and hypergraphs, certain constraint satisfaction problems and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard.
---
paper_title: Optimal approximation for the submodular welfare problem in the value oracle model

paper_content:

In the Submodular Welfare Problem, m items are to be distributed among n players with utility functions wi: 2[m] → R+. The utility functions are assumed to be monotone and submodular. Assuming that player i receives a set of items Si, we wish to maximize the total utility ∑i=1n wi(Si). In this paper, we work in the value oracle model where the only access to the utility functions is through a black box returning wi(S) for a given set S. Submodular Welfare is in fact a special case of the more general problem of submodular maximization subject to a matroid constraint: max{f(S): S ∈ I}, where f is monotone submodular and I is the collection of independent sets in some matroid. ::: For both problems, a greedy algorithm is known to yield a 1/2-approximation [21, 16]. In special cases where the matroid is uniform (I = S: |S| ≤ k) [20] or the submodular function is of a special type [4, 2], a (1-1/e)-approximation has been achieved and this is optimal for these problems in the value oracle model [22, 6, 15]. A (1-1/e)-approximation for the general Submodular Welfare Problem has been known only in a stronger demand oracle model [4], where in fact 1-1/e can be improved [9]. ::: In this paper, we develop a randomized continuous greedy algorithm which achieves a (1-1/e)-approximation for the Submodular Welfare Problem in the value oracle model. We also show that the special case of n equal players is approximation resistant, in the sense that the optimal (1-1/e)-approximation is achieved by a uniformly random solution. Using the pipage rounding technique [1, 2], we obtain a (1-1/e)-approximation for submodular maximization subject to any matroid constraint. The continuous greedy algorithm has a potential of wider applicability, which we demonstrate on the examples of the Generalized Assignment Problem and the AdWords Assignment Problem.
---
paper_title: Unbalanced Graph Cuts

paper_content:

We introduce the Minimum-size bounded-capacity cut (MinSBCC) problem, in which we are given a graph with an identified source and seek to find a cut minimizing the number of nodes on the source side, subject to the constraint that its capacity not exceed a prescribed bound B. Besides being of interest in the study of graph cuts, this problem arises in many practical settings, such as in epidemiology, disaster control, military containment, as well as finding dense subgraphs and communities in graphs. ::: ::: In general, the MinSBCC problem is NP-complete. We present an efficient $(\frac{1}{{\rm \lambda}},\frac{1}{1-{\rm \lambda}})$-bicriteria approximation algorithm for any 0 < λ < 1; that is, the algorithm finds a cut of capacity at most $\frac{1}{{\rm \lambda}}B$, leaving at most $\frac{1}{1-{\rm \lambda}}$ times more vertices on the source side than the optimal solution with capacity B. In fact, the algorithm’s solution either violates the budget constraint, or exceeds the optimal number of source-side nodes, but not both. For graphs of bounded treewidth, we show that the problem with unit weight nodes can be solved optimally in polynomial time, and when the nodes have weights, approximated arbitrarily well by a PTAS.
---
paper_title: Unbalanced Graph Cuts

paper_content:

We introduce the Minimum-size bounded-capacity cut (MinSBCC) problem, in which we are given a graph with an identified source and seek to find a cut minimizing the number of nodes on the source side, subject to the constraint that its capacity not exceed a prescribed bound B. Besides being of interest in the study of graph cuts, this problem arises in many practical settings, such as in epidemiology, disaster control, military containment, as well as finding dense subgraphs and communities in graphs. ::: ::: In general, the MinSBCC problem is NP-complete. We present an efficient $(\frac{1}{{\rm \lambda}},\frac{1}{1-{\rm \lambda}})$-bicriteria approximation algorithm for any 0 < λ < 1; that is, the algorithm finds a cut of capacity at most $\frac{1}{{\rm \lambda}}B$, leaving at most $\frac{1}{1-{\rm \lambda}}$ times more vertices on the source side than the optimal solution with capacity B. In fact, the algorithm’s solution either violates the budget constraint, or exceeds the optimal number of source-side nodes, but not both. For graphs of bounded treewidth, we show that the problem with unit weight nodes can be solved optimally in polynomial time, and when the nodes have weights, approximated arbitrarily well by a PTAS.
---

Title: Submodular Functions: Extensions, Distributions, and Algorithms. A Survey

Section 1: Introduction
Description 1: Introduce the fundamental concepts and importance of submodular functions, and outline the purpose and structure of the survey.

Section 2: Contributions
Description 2: Present the contributions of the survey, including a common framework for viewing results on optimizing submodular functions.

Section 3: Preliminaries
Description 3: Define submodular functions, provide examples, and discuss the value oracle model.

Section 4: Polytopes and Integrality Gaps
Description 4: Discuss the concept of polytopes, integrality gaps, and their roles in combinatorial optimization.

Section 5: Matroids
Description 5: Introduce matroids, their properties, and their significance in the study of submodular functions.

Section 6: Extensions and Distributions
Description 6: Explain various extensions of submodular functions and their connections to distributions over the ground set.

Section 7: The Convex Closure, Lovász Extension, and Chain Distributions
Description 7: Define the convex closure, Lovász extension, and chain distributions, and explain their algorithmic implications.

Section 8: Equivalence of Lovász Extension and Convex Closure
Description 8: Show the equivalence between the Lovász extension and the convex closure for submodular functions, and discuss the implications.

Section 9: The Concave Closure
Description 9: Define the concave closure, discuss its properties, and explain the computational challenges associated with it.

Section 10: Defining the Multilinear Extension
Description 10: Introduce the multilinear extension of submodular functions, and explain its properties and benefits.

Section 11: Useful Properties of the Multilinear Extension
Description 11: Elaborate on the properties of the multilinear extension useful for maximizing submodular functions.

Section 12: Algorithmic Implications
Description 12: Discuss the algorithms for minimizing and maximizing submodular functions using the described extensions.

Section 13: Minimizing Submodular Functions
Description 13: Detail approaches and algorithms for minimizing submodular functions.

Section 14: Maximizing Monotone Submodular Functions Subject to a Matroid Constraint
Description 14: Describe the problem of maximizing monotone submodular functions over matroid constraints, and present the relevant algorithms.

Section 15: A 2-approximation algorithm
Description 15: Present a 2-approximation algorithm for minimizing nonnegative, symmetric submodular functions subject to a cardinality constraint.

Section 16: Conclusion
Description 16: Summarize the survey’s findings, emphasize the utility of extensions and distributions in submodular function optimization, and suggest directions for future research.