Submodular Function Maximization

Abstract

In this chapter we will introduce submodularity and some of its generalizations, illustrate how it arises in various applications, and discuss algorithms for optimizing submodular functions. Submodularity is a property of set functions with deep theoretical consequences and far-reaching applications. At first glance it seems very similar to concavity, in other ways it resembles convexity. It appears in a wide variety of applications: in Computer Science it has recently been identified and utilized in domains such as viral marketing [39], information gathering [44], image segmentation [10, 40, 36], document summarization [56], and speeding up satisfiability solvers [73]. Our emphasis in this chapter is on maximization; there are many important results and applications related to minimizing submodular functions that we do not cover. As a concrete running example, we will consider the problem of deploying sensors in a drinking water distribution network (see Figure 3.1) in order to detect contamination. In this domain, we may have a model of how contaminants, accidentally or maliciously introduced into the network, spread over time. Such a model then allows to quantify the benefit f(A) of deploying sensors at a particular set A of locations (junctions or pipes in the network) in terms of the detection performance (such as average time to detection). Based on this notion of utility, we then wish to find an optimal subset A ⊆ V of locations maximizing the utility, max A f(A) , subject to some constraints (such as bounded cost). This application requires solving a difficult real-world optimization problem, that can be handled with the techniques discussed in this chapter (Krause et al. [49] show in detail how submodular optimization can be applied in this domain.)