Book contents
- Frontmatter
- Contents
- Contributors
- Introduction
- Part 1 Graphical Structure
- Part 2 Language Restrictions
- 3 Submodular Function Maximization
- 4 Tractable Valued Constraints
- 5 Tractable Knowledge Representation Formalisms
- Part 3 Algorithms and their Analysis
- Part 4 Tractability in Some Specific Areas
- Part 5 Heuristics
3 - Submodular Function Maximization
from Part 2 - Language Restrictions
Published online by Cambridge University Press: 05 February 2014
- Frontmatter
- Contents
- Contributors
- Introduction
- Part 1 Graphical Structure
- Part 2 Language Restrictions
- 3 Submodular Function Maximization
- 4 Tractable Valued Constraints
- 5 Tractable Knowledge Representation Formalisms
- Part 3 Algorithms and their Analysis
- Part 4 Tractability in Some Specific Areas
- Part 5 Heuristics
Summary
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, maxAf(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.)
- Type
- Chapter
- Information
- TractabilityPractical Approaches to Hard Problems, pp. 71 - 104Publisher: Cambridge University PressPrint publication year: 2014
- 258
- Cited by